In the Yunity Game Engine, you're managing 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 events. Each event is represented by a pair of objects where . The event toggles the interaction status between these two objects:
- If objects and could interact before the event, they can no longer interact after the event.
- Conversely, if objects and 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 , it must be either friendly or unfriendly with .
- An object is friendly with if it can interact with every object in .
- An object is unfriendly with if it can interact with no object in .
After each event, your job is to find the smallest possible number of interaction groups in a valid partitioning.
Constraints
For all subtasks:
Subtask 1 [20%]
Subtask 2 [30%]
An unordered pair will not appear more than once.
Subtask 3 [50%]
No additional constraints.
Input Specification
The first line contains two space-seperated integers and , representing the number of objects and the number of queries.
Each of the following lines contains a query represented by two different integers and , 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 st and nd objects can no longer interact with each other. One optimal partitioning is shown above, with groups. The blue group is independent, and the red group is social.
Following the second query, the st and rd objects can no longer interact with each other. One optimal partitioning is shown above.
- The blue group is social and independent. Objects and are unfriendly with the blue group. Objects and are friendly with the blue group.
- The red group is independent. Object is unfriendly with the red group, and objects and are friendly with the red group.
- The yellow group is social. Objects , , and are all friendly with the yellow group.
Comments