DMOPC '22 Contest 1 P3 - Group Project

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

You are the teacher of a class of N students, all but M pairs of which are friends. A friend group is a group of 3 or 4 people such that each person in the group is friends with at least 2 other people in the group. Your next class assignment requires the students to work in groups of 4. To "encourage new friendships and social interaction," you want to see if you can pick a group of 4 that does not contain a friend group. Of course, friendships in the class are constantly evolving. Thus, you would like to determine whether it is still possible to pick a group of 4 that does not contain a friend group after each of Q changes.

Constraints

4 \le N \le 4 \times 10^5

0 \le M, Q \le 4 \times 10^5

1 \le u_i, v_i \le N

Subtask 1 [50%]

4 \le N \le 5 \times 10^3

0 \le M, Q \le 5 \times 10^3

Subtask 2 [50%]

No additional constraints.

Input Specification

The first line contains 3 integers N, M, and Q.

The next M lines each contain 2 integers u_i and v_i, indicating that students u_i and v_i are not friends. All pairs not mentioned here are originally friends.

The next Q lines each contain 2 integers u_i and v_i, indicating a change in the friendship status of students u_i and v_i; they become friends if they weren't friends previously and vice versa.

Output Specification

Output Q+1 lines, the i-th line containing the answer after the first i-1 changes. The answer should be either YES if it is possible to pick a group of 4 that does not contain a friend group or NO otherwise.

Sample Input

6 3 1
1 2
1 3
2 4
1 2

Sample Output

YES
NO

Explanation for Sample

Initially, the graph looks like this (with edges denoting a friendship):

It can be shown that there is no friend group within the group of students (1, 2, 3, 4). However, after the update:

All groups of 4 contain a friend group, so it is impossible to pick a group of 4 that does not contain a friend group.


Comments

There are no comments at the moment.