In the Yunity Game Engine, you're managing ~N~ objects (characters, entities, etc.) within a virtual game environment. Initially, every object can interact (collide) with every other object. However, throughout the gameplay, you receive ~Q~ events. Each event is represented by a pair of objects ~(a, b)~ where ~a ≠ b~. The event toggles the interaction status between these two objects:

• If objects ~a~ and ~b~ could interact before the event, they can no longer interact after the event.
• Conversely, if objects ~a~ and ~b~ could not interact before the event, they will be able to interact after the event.

Your job is to partition the objects into interaction groups. Each group must be social or independent.

• A social group is one for which every pair of distinct objects in the group can interact with each other.
• An independent group is one for which every pair of distinct objects in the group cannot interact with each other.

Note that groups of size one are both social and independent.

Additionally, for every object not in a group ~G~, it must be either friendly or unfriendly with ~G~.

• An object is friendly with ~G~ if it can interact with every object in ~G~.
• An object is unfriendly with ~G~ if it can interact with no object in ~G~.

After each event, your job is to find the smallest possible number of interaction groups in a valid partitioning.

Constraints

For all subtasks:

~2 \le N \le 5 \times 10^5~

~1 \le Q \le 5 \times 10^5~

~1 \le a,b \le N; a ≠ b~

Subtask 1 [20%]

~2 \le N \le 10^4~

~1 \le Q \le 2 \times 10^3~

Subtask 2 [30%]

An unordered pair ~(a,b)~ will not appear more than once.

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains two space-seperated integers ~N~ and ~Q~, representing the number of objects and the number of queries.

Each of the following ~Q~ lines contains a query represented by two different integers ~a~ and ~b~, separated by a space. These integers indicate a pair of objects whose interaction status will be toggled.

Output Specification

After each event, output the number of interaction groups in a minimal partitioning of the objects.

Sample Input

5 4
1 2
1 3
1 2
4 5

Sample Output

2
3
2
3

Sample Explanation

After the first query, the ~1~st and ~2~nd objects can no longer interact with each other. One optimal partitioning is shown above, with ~2~ groups. The blue group is independent, and the red group is social.

Following the second query, the ~1~st and ~3~rd objects can no longer interact with each other. One optimal partitioning is shown above.

• The blue group is social and independent. Objects ~2~ and ~3~ are unfriendly with the blue group. Objects ~4~ and ~5~ are friendly with the blue group.
• The red group is independent. Object ~1~ is unfriendly with the red group, and objects ~4~ and ~5~ are friendly with the red group.
• The yellow group is social. Objects ~1~, ~2~, and ~3~ are all friendly with the yellow group.