| Submit | All submissions | Best solutions | Back to list |
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