Walks and Queries

Seongseo picked $N$ candidate places near Soongsil University for a room search and numbered them from $1$ to $N$. Each place has exactly one room. Many factors matter when choosing a room, but Seongseo values freedom to walk above all else.

Path $(a,b)$ connects two different places $a$ and $b$. Walking from $a$ to $b$ takes $1$ unit of time, and walking from $b$ to $a$ also takes $1$ unit of time. Once you start walking, you cannot turn or stop midway. You must walk for exactly $1$ unit of time and arrive at the other end.

Walk starts at some place $u$, follows paths, and finally returns to $u$. A walk may visit the same place or path many times, but you cannot pause for even a moment.

Seongseo looks around the places and adds paths with a nice atmosphere to a personal path list. A satisfying walk uses only the paths on that list.

Seongseo wants to walk for a long time and return at a chosen moment. Room $u$ has high walking freedom if, for every integer $t$ of at least $10^6$, there is a satisfying walk that starts at $u$ and takes exactly $t$ units of time.

The path list starts empty. Each time Seongseo finds a good path, the path is added to the list. After each change, find how many rooms have high walking freedom.

Specifically, you must process $Q$ queries of the following form.

• a b: Add path $(a,b)$ to the path list. Then print the number of rooms with high walking freedom.

For example, suppose there are $6$ rooms and the path list is $\{(1,2), (2,3), (1,3), (4,5)\}$. The figure above shows this case.

Room $6$ has no satisfying walk that takes $10^6$ units of time, so its walking freedom is not high.

Rooms $4$ and $5$ have satisfying walks that take $10^6$ or $10^6+2$ units of time, but none that take $10^6+1$ or $10^6+3$ units of time. Their walking freedom is not high.

Rooms $1$, $2$, and $3$ have satisfying walks for $10^6$, $10^6+1$, $10^6+2$, $10^6+3$, and so on. Their walking freedom is high.

So in this figure, the number of rooms with high walking freedom is $3$.

The first line contains $N$ and $Q$, the number of places and the number of queries, separated by a space.

Each of the next $Q$ lines contains $a_i$ and $b_i$, the two places connected by the path added in the $i$-th query, separated by a space.

For each query, print the answer on its own line.

• $2 \leq N \leq 3 \times 10^5$
• $1 \leq Q \leq 6 \times 10^5$
• $1 \leq a_i < b_i \leq N$ $(1 \leq i \leq Q)$
• No query is given more than once.
• All given numbers are integers.

The input and output are large, so use the fast I/O method described in the language guide on pages 2 to 4 of the problem booklet.