Road Construction

Input

The first line has two integers $n$ ($1$ ≤ $n$ ≤ 10^5) and $m$ ($1$ ≤ $m$ ≤ 2 \cdot 10^5): the number of cities and roads. The cities are numbered $1$, $2$, ..., $n$.

Then, there are $m$ lines describing the new roads. Each line has two integers $a$ and $b$ ($1$ ≤ $a$, $b$ ≤ $n$): a new road is constructed between cities $a$ and $b$.

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

Output

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

Examples