Given an undirected graph with ~n~ vertices and ~m~ edges. Vertices are numbered from ~0~ to ~n-1~. Determine connected components in the given graph.

Input

• The first line consists of two positive integers, the number ~n~ vertices ~(0 < n < 10^5)~ and the number of edges ~m~ ~(0 < m \le 2\times 10^5)~.
• Then there are ~m~ lines, each containing two integers ~u~ and ~v~ representing an edge which connects ~u~ and ~v~.~(u,v < 10^5)~.

Output

• For each component , print the smallest vertice and the number of vertices in the component.

Example Input

3 1
1 2 

Example Output

0 1
1 2