C. Cardinality
time limit per test
10 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is an interactive problem.

There are $$$n$$$ sets numbered $$$1$$$ to $$$n$$$, the $$$i$$$-th of them containing only the integer $$$i$$$. You need to process $$$q$$$ queries. The $$$i$$$-th query (1-indexed) is described by a pair of integers $$$(X_i, Y_i)$$$. It creates a set number $$$n + i$$$, which consists of a union of integers from sets $$$X_i$$$ and $$$Y_i$$$.

Each time you create a new set, you must report the number of different integers in this set. You don't need to report the exact result. If the correct size of the set is $$$A$$$ and you print integer $$$B$$$, it will be accepted if $$$0.5 \cdot A \le B \le 2.0 \cdot A$$$.

Flushing the output could be costly on some Judging Systems, so all queries are split into batches of size 50. Your solution should read the first 50 queries, print the answers for all of them, flush the output, read the second batch of 50 queries, print the answers for them, flush the output, and so on. The last batch could consist of less than 50 queries.

The interactor is not adaptive, which means for each test, the sequence of queries is always the same for all runs.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 50\,000, 1 \le q \le 5 \cdot 10^5$$$) — the initial number of sets and the number of queries.

The next $$$q$$$ lines contain queries. The $$$i$$$-th of them contains two integers $$$X_i$$$ and $$$Y_i$$$ ($$$1 \le X_i, Y_i \lt n + i$$$).

Output

For each query, print one integer in a separate line — your estimate of the size of the created set.

Don't forget to flush output after every 50th query!

Example
Input
4 5
1 2
2 3
5 6
6 7
4 7
Output






2
2
3
3
4