30376번 - Odd trip plans 다국어

문제

JAG is a country with $n$ airports numbered through 1ドル$ to $n$. There are some airways, each of which connects two different airports bidirectionally. In other words, if an airway connects airports $u$ and $v,ドル a passenger can move either from $u$ to $v$ or from $v$ to $u$ in a single flight. Airways may be newly established or abolished.

Mr. Oddytrip, who is a traveler loving odd numbers, plans a trip from an airport to another one by flights. Let’s say that he boards $k$ flights: A flight from $p_1$ airport to $p_2,ドル then from $p_2$ to $p_3,ドル then from $p_3$ to $p_4,ドル and so on, and finally from $p_k$ to $p_{k+1}$. This trip plan, which begins with $p_1$ and ends with $p_{k+1},ドル is written as $p_1 \rightarrow p_2 \rightarrow p_3 \rightarrow p_4 \rightarrow \cdots \rightarrow p_k \rightarrow p_{k+1}$. According to his aesthetics, a trip plan is beautiful if each of $n$ airports appear an odd number of times in the trip plan. For example, if $n = 6,ドル trip plans 3ドル \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 1 \rightarrow 2$ and 1ドル \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 6$ are beautiful while 1ドル \rightarrow 3 \rightarrow 6$ and 1ドル \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 5 \rightarrow 6$ aren’t. In particular, each of the $n$ airports appears at least one in a beautiful trip plan.

Initially, there are $m$ airways. Then, you are given $q$ queries, which should be processed in the order they are given. Each query is of one of the two kinds below:

• 1ドル$ $x$ $y$: The existence of the airway between airports $x$ and $y$ changes. If there is already an airway between airports $x$ and $y,ドル then such an airway is abolished. In other words, Mr. Oddytrip is no longer able to board the direct flight between airports $x$ and $y$ (until it is newly established again). On the other hand, if there wasn’t such an airway before, an airway between airports $x$ and $y$ is newly established. In other words, Mr. Oddytrip can board a direct flight between airports $x$ and $y$ (until it is abolished again).
• 2ドル$ $x$ $y$: You have to determine whether there can be a beautiful trip plan which begins with airport $x$ and ends with airport $y$ using the airways which are available at that time.

입력

The input consists of a single test case of the following format.

$n$ $m$ $q$

$u_1$ $v_1$

$\vdots$

$u_m$ $v_m$

$t_1$ $x_1$ $y_1$

$\vdots$

$t_q$ $x_q$ $y_q$

The first line consists of three integers $n,ドル $m$ and $q$ (2ドル \le n \le 100,000円,ドル 0ドル \le m \le 100,000円,ドル 1ドル \le q \le 100,000円$), where $n$ is the number of airports in JAG country, $m$ is the number of airways which are initially available, and $q$ is the number of queries.

The $i$-th of the following $m$ lines consists two integers $u_i$ and $v_i$ (1ドル \le u_i < v_i \le n$) representing that an airway between airports $u_i$ and $v_i$ is initially available. It is guaranteed that these $m$ airways are distinct.

The $j$-th of the following $q$ lines consists of three integers $t_j,ドル $x_j$ and $y_j$ (1ドル \le t_j \le 2,ドル 1ドル \le x_j < y_j \le n$) representing the type of the query and the numbers of two airports as described above. It is guaranteed that there is at least one query where $t_j=2$.

출력

For each query where $t_j = 2,ドル print “Yes” in a single line if there can be a beautiful trip plan which begins with airport $x$ and ends with airport $y$. Otherwise, print “No” in a single line.

제한

힌트