CSES - Road Construction
  • Time limit: 1.00 s
  • Memory limit: 512 MB

There are nn cities and initially no roads between them. However, every day a new road will be constructed, and there will be a total of mm 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 nn and mm: the number of cities and roads. The cities are numbered 1,2,,n1,2,\dots,n.

Then, there are mm lines describing the new roads. Each line has two integers aa and bb: a new road is constructed between cities aa and bb.

You may assume that every road will be constructed between two different cities.

Output

Print mm lines: the required information after each day.

Constraints

  • 1n1051 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5
  • 1a,bn1 \le a,b \le n

Example

Input:

5 3
1 2
1 3
4 5

Output:

4 2
3 3
2 3