## DMOPC '22 Contest 1 P3 - Group Project

View as PDF

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

Author:
Problem types

You are the teacher of a class of students, all but pairs of which are friends. A friend group is a group of or people such that each person in the group is friends with at least other people in the group. Your next class assignment requires the students to work in groups of . To "encourage new friendships and social interaction," you want to see if you can pick a group of 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 that does not contain a friend group after each of changes.

#### Constraints

##### Subtask 2 [50%]

No additional constraints.

#### Input Specification

The first line contains integers , , and .

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

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

#### Output Specification

Output lines, the -th line containing the answer after the first changes. The answer should be either YES if it is possible to pick a group of 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 . However, after the update:

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

## Comments

There are no comments at the moment.