题目描述

园艺师 Lin 维护着一株图论意义下的仙人掌：它是一张简单无向连通图，并且每条边至多属于一个简单环。

Lin 可以对这株仙人掌执行两类操作：

1. 选择当前图中一个度数为奇数的顶点，删除所有与它相连的边；
2. 复制当前整张图，并把原图中的每个顶点与复制图中对应的顶点相连。

第二类操作非常昂贵，因此最多只能使用一次。第一类操作可以使用任意多次，顺序任意。

更具体地说，若当前图有 $n$ 个顶点，编号为 $1$ 到 $n$，第二类操作会新增 $n$ 个顶点，编号为 $n+1$ 到 $2n$。对于原图中的每条边 $(u,v)$，复制图中也会加入边 $(u+n,v+n)$。最后，再加入

如果操作前图有 $n$ 个顶点和 $m$ 条边，那么操作后图有 $2n$ 个顶点和 $2m+n$ 条边。

Lin 希望通过一系列操作，使最终图中的边数尽可能少。请输出任意一种最优操作序列。

输入格式

第一行包含两个整数 $n,m$，表示初始图的顶点数和边数。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示一条无向边。

保证输入图连通，没有自环和重边，并且是一棵仙人掌。

输出格式

第一行输出两个整数 $m'$ 和 $K$，分别表示最终图中剩余的边数，以及操作总数。

接下来输出 $K$ 行，每行描述一个操作：

• 若执行第一类操作并选择顶点 $x$，输出 1 x；
• 若执行第二类操作，输出 2。

如果存在多种最优方案，输出任意一种即可。

数据范围

• $1\le n\le 3\cdot 10^5$；
• $n-1\le m\le \frac{3(n-1)}{2}$；
• $1\le u,v\le n$；
• 输入图连通、无自环、无重边，且是一棵仙人掌。

样例 1

输入

3 3
1 2
1 3
2 3

输出

0 6
2
1 1
1 5
1 2
1 4
1 3

样例 2

输入

7 7
1 2
1 3
2 3
2 4
2 5
3 6
3 7

输出

0 14
1 4
1 5
1 6
1 7
2
1 1
1 4
1 5
1 6
1 7
1 9
1 2
1 8
1 3