H. Seeking Allies
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
In the middle of difficulty lies opportunity. We make alliances with the hope of avoiding bloodshed.
— Albert Einstein and Sun Tzu, The Art of War

A shadow falls, bringing the end to the entire world. To struggle for survival, people decided to seek allies.

There are $$$n$$$ people standing in a row, who are initially unfamiliar with each other.

Also, there are $$$d$$$ conditions, the $$$i$$$-th of them restricting that $$$p_i$$$ is familiar with $$$q_i$$$.

Now, it's your decision time. Let's define that:

Your one operation is to choose two integers $$$i, j$$$ $$$(1 \leq i, j \leq n, i \neq j)$$$, such that the $$$i$$$-th person and the $$$j$$$-th person were not familiar before, and make them familiar.

Note that if $$$a$$$ is familiar with $$$b$$$ and $$$b$$$ is familiar with $$$c$$$, then $$$a$$$ is familiar with $$$c$$$.

At time $$$i$$$ $$$(1 \leq i \leq d)$$$, you can do at most $$$i$$$ operations, but you need to satisfy the conditions from $$$1$$$ to $$$i$$$ (inclusive). After the last operation of each time $$$i$$$, you need to calculate the maximal number of people that one person can be familiar with.

Note that the operations of each $$$i$$$ are independent. It means that before you start your first operation at each time $$$i$$$, you need to assume that the $$$n$$$ people are unfamiliar with each other.

Input

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10 ^ 4)$$$, denoting the number of test cases.

The first line of each test case contains two integers $$$n$$$, $$$d$$$ $$$(2 \leq n \leq 10 ^ 5, 1 \leq d \leq n - 1)$$$.

The $$$i$$$-th of the next $$$d$$$ lines contains two integers $$$p_i$$$, $$$q_i$$$ $$$(1 \leq p_i, q_i \leq n, p_i \neq q_i)$$$, denoting the $$$i$$$-th condition.

It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \times 10 ^ 5$$$.

Output

For each test case, output $$$d$$$ lines, the $$$i$$$-th of them contains one integer $$$x$$$, denoting the maximal number of people that one person can be familiar with at time $$$i$$$.

Example
Input
2
7 6
1 2
3 4
2 4
7 6
6 5
1 7
10 8
1 2
2 3
3 4
1 4
6 7
8 9
8 10
1 4
Output
1
1
3
3
3
6
1
2
3
4
5
5
6
8
Note

The explanation for the first test case:

Visual explanation

In this explanation, the circles and the numbers in them denote a person with the corresponding number. The line denotes that you decided to make two connected people familiar. The person marked with red has the maximal number of people that one person can be familiar with.

These are not the only correct ways.