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.