Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

K. Dynamic Reachability
time limit per test
12 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a directed graph with $$$n$$$ vertices and $$$m$$$ edges, the vertices of which are labeled by $$$1,2,\dots,n$$$. The color of each edge is either black or white. Initially, all the $$$m$$$ edges are colored black.

You need to perform $$$q$$$ operations. Each operation is one of the following:

  • "1 $$$k$$$" ($$$1 \leq k \leq m$$$): Change the color of the $$$k$$$-th edge in the input from black to white and vice versa.
  • "2 $$$u$$$ $$$v$$$" ($$$1 \leq u,v \leq n$$$, $$$u\neq v$$$): You need to answer whether vertex $$$u$$$ can reach vertex $$$v$$$ without passing any white edge.
Input

The input contains only a single case.

The first line contains three integers $$$n,m$$$ and $$$q$$$ ($$$2 \leq n \leq 50\,000$$$, $$$1\leq m,q\leq 100\,000$$$), denoting the number of vertices, the number of edges, and the number of operations.

Each of the following $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1\leq u_i,v_i\leq n$$$, $$$u_i\neq v_i$$$, $$$1\leq i\leq m$$$), denoting a directed edge from vertex $$$u_i$$$ to vertex $$$v_i$$$.

Each of the next $$$q$$$ lines describes an operation in formats described in the statement above.

Output

For each query, print a single line. If vertex $$$u$$$ can reach vertex $$$v$$$ without passing any white edge, print "YES". Otherwise, print "NO".

Example
Input
5 6 7
1 2
1 3
2 4
3 4
3 5
4 5
2 1 5
2 2 3
1 3
1 4
2 1 4
1 3
2 1 5
Output
YES
NO
NO
YES