- Time limit: 1.00 s
- Memory limit: 512 MB
There are cities and initially no roads between them. However, every day a new road will be constructed, and there will be a total of roads.
A component is a group of cities where there is a route between any two cities using the roads. After each day, your task is to find the number of components and the size of the largest component.
Input
The first input line has two integers and : the number of cities and roads. The cities are numbered .
Then, there are lines describing the new roads. Each line has two integers and : a new road is constructed between cities and .
You may assume that every road will be constructed between two different cities.
Output
Print lines: the required information after each day.
Constraints
Example
Input:
5 3 1 2 1 3 4 5
Output:
4 2 3 3 2 3