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

Input

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

Output

1 1
1 1
2 4
1 1

Example 2

Input

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

Output

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