图 $G$ 的 $b$-折着色（$b$-fold coloring）是指为 $G$ 的每个顶点分配一个大小为 $b$ 的颜色集合，使得相邻顶点分配的集合不相交。$a:b$-着色是一种 $b$-折着色，其中所有分配的颜色集合都是一个大小为 $a$ 的全集中的子集。

仙人掌图（cactus）是一个连通图，其中每条边最多属于一个简单环。

给定一个仙人掌图，请找到一种 $a:b$-着色，使得在 $1 \le b \le 1000$ 的条件下，比值 $\frac{a}{b}$ 最小。如果存在多个具有最小比值的合适 $a:b$-着色，输出其中任意一个。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 1000, 1 \le m \le 1500$)，分别表示图的顶点数和边数。

接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，描述顶点 $u$ 和 $v$ 之间的一条边。

保证给定的图是一个没有自环和重边的仙人掌图。

输出格式

第一行输出两个整数 $a$ 和 $b$ ($1 \le a \le 10^6, 1 \le b \le 1000$)。可以证明，在给定的限制条件下，最优解中的 $a$ 不会超过 $10^6$。

接下来 $n$ 行，每行应包含 $b$ 个 $1$ 到 $a$ 之间的不同整数。第 $i$ 行应描述分配给顶点 $i$ 的颜色集合，顺序任意。

样例

输入 1

2 1
1 2

输出 1

2 1
1
2

输入 2

3 3
1 2
2 3
1 3

输出 2

6 2
2 5
1 6
3 4

输入 3

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

输出 3

3 1
3
1
2
1
3

输入 4

4 3
1 2
1 3
1 4

输出 4

4 2
1 3
2 4
2 4
2 4