Given an undirected graph with ~n~ vertices and ~m~ edges. Vertices are numbered from ~0~ to ~n-1~. Write a program to calculate the number of vertices and edges of each component.

Input

• The first line contains the number of vertices ~n~ ~(1 ≤ n ≤ 10^5)~, the number of edges ~m~ ~(1 ≤ m ≤ 2 \times 10^5)~.
• Each of the next ~m~ lines contains ~2~ integers ~u~, ~v~ representing an edge between ~u~ and ~v~ ~(0 ≤ u,v ≤ n)~.

Output

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

Sample Input

3 1
1 2

Sample Output

0 1 0
1 2 1