Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

EICONP1 - Connected components II

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<105) and the number of edges m  (0<m<2x105).

Then there are m lines, each containing two integers u and v  representing an edge which connects u and v.(u,v<105).

Output

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

Example

Input:
3 1
1 2 
Output:
0 1
1 2

Added by:Ha Minh Ngoc
Date:2015-12-31
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.