Attempt

Please login to see your submissions result.

Problem

There are ~n~ computers and initially no network routes between them. However, every day a new network route will be constructed, and there will be a total of ~m~ routes.

A grouped network component is a group of computers where there is a network route between any two computers using the network routes. After each day, your task is to find the number of grouped network components and the size of the largest component.

Input

First line contains two postitive integers ~n~ and ~m~ is the number of computers and network routes. The computers are numbered ~1,2,\dots,n~.

Next, there are ~m~ lines describing the new network routes. Each line has two integers ~a~ and ~b~ denoted a new network routes is constructed between computers ~a~ and ~b~.

You may assume that every routes will be constructed between two different computers.

Output

Print ~m~ lines: the required information after each day.

Constraints

~1 \leq n \leq 2 \times 10^5~.
~1 \leq m \leq (n-1000)~.
~1 \leq a, b \leq n~.

Sample