仙人掌图（cactus）是一种简单的无向连通图，其中每条边最多属于一个简单环。 现在，有一个仙人掌图支持以下两种操作：

1. 选择图中一个度数为奇数的顶点，并移除所有与该顶点相连的边。
2. 复制当前的图，然后在当前图和副本的对应顶点之间添加额外的边，从而形成一个新图。形式化地说，假设当前图共有 $n$ 个顶点，编号为 $1$ 到 $n$。首先，添加 $n$ 个编号为 $n+1$ 到 $2n$ 的新顶点。然后，对于当前图中的每条边 $(u, v)$，添加一条边 $(u+n, v+n)$。最后，添加边 $(1, n+1), (2, n+2), \dots, (n, 2n)$。如果当前图有 $n$ 个顶点和 $m$ 条边，则新图有 $2n$ 个顶点和 $2m+n$ 条边。

由于第二种操作代价高昂，它最多只能使用一次。第一种操作可以以任意顺序使用任意次数。 请找到一个操作序列，使得在执行完序列中的所有操作后，最终图的边数最少。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，分别表示初始图的顶点数和边数（$1 \le n \le 3 \cdot 10^5$，$n-1 \le m \le \frac{3(n-1)}{2}$）。 接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$，表示一条边的两个端点（$1 \le u, v \le n$）。 该图是连通的，且不包含重边和自环。

输出格式

第一行输出两个整数 $m'$ 和 $K$，分别表示最终图中剩余的边数和总操作次数。 接下来输出 $K$ 行，每行代表一个操作：

1. 当对顶点 $x$ 使用第一种操作时，输出 “1 $x$”。
2. 当使用第二种操作时，输出 “2”。

如果存在多个最优解，输出其中任意一个即可。

样例

样例输入 1

3 3
1 2
1 3
2 3

样例输出 1

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

样例输出 2

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