Copy Paste???

You are given an undirected graph with $n$ nodes and $m$ edges. What is the distance from node $1$ to every other node, and how many paths with that length exist between $1$ and that node?

A path has no repeating edges or nodes.

Input

The first line contains the integers $n$ and $m$.

The following $m$ lines contain integers $a, b$ indicating an undirected edge from node $a$ to node $b$.

The nodes are numbered $1$ through $n$.

It is guaranteed that there is a path from $1$ to every other node.

Output

Output $n-1$ lines. The $i$-th line should contain the distance from node $1$ to node $i + 1$, and the number of paths of that length between node $1$ and node $i + 1$.

Constraints

• $1 \le a,b \le n \le 10000$
• $1 \le m \le 10^5$

Example 1

5 10
1 2
2 3
3 4
4 5
5 1
4 4
2 3
2 4
5 4
3 1

1 1
1 1
2 4
1 1

Example 2

10 20
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 1
8 10
4 6
3 6
9 8
4 5
6 10
8 10
8 9
1 7
4 10

1 1
2 1
2 1
3 4
2 2
1 1
2 3
2 1
1 1