시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB111100.000%

문제

«Contest should be comparable with regional competitions»- they say. Well, with this problem, this one should feel really NEERC.

A $b$-fold coloring of a graph $G$ is an assignment of sets of colors of size $b$ to vertices of $G$ such that adjacent vertices are assigned with disjoint sets. An $a$:$b$-coloring is a $b$-fold coloring such that all assigned sets of colors are subsets of a universal set of size $a$.

A cactus is a connected graph in which every edge belongs to at most one simple cycle.

You are given a cactus. Find its $a$:$b$-coloring that minimizes the ratio $\frac{a}{b}$ among colorings with $1 \leq b \leq 1000$. If there are multiple suitable $a$:$b$-colorings with the smallest possible ratio, output any of them.

입력

The first line contains two integers $n$ and $m$ ($2 \leq n \leq 1000, 1 \leq m \leq 1500$), the number of vertices and the number of edges in the graph respectively.

Each of the next $m$ lines contains two integers $u$ and $v$ ($1 \leq u, v \leq n$) describing an edge between vertices $u$ and $v$.

It is guaranteed that the given graph is a cactus without loops and multiple edges.

출력

In the first line print two integers $a$ and $b$ ($1 \leq a \leq 10^6, 1 \leq b \leq 1000$). It can be proven, that in an optimal answer $a$ will never exceed $10^6$ under given limitations.

Each of the next $n$ lines should contain $b$ distinct numbers in the range from 1 to $a$. $i$-th of the lines should describe the set of colors assigned to the vertex $i$ in an arbitrary order.

예제 입력 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