In the Yunity Game Engine, you're managing
- 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
- 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
Subtask 3 [50%]
No additional constraints.
Input Specification
The first line contains two space-seperated integers
Each of the following
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

Following the second query, the
- 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