P15728 [JAG 2023 Summer Camp #3] Odd trip plans

JAG 是一个拥有 $n$ 个机场的国家，机场编号为 $1$ 到 $n$。存在若干条航线，每条航线双向连接两个不同的机场。换句话说，如果一条航线连接了机场 $u$ 和 $v$，乘客可以乘坐一次航班从 $u$ 前往 $v$，或者从 $v$ 前往 $u$。航线可能会被新建立或废除。 热爱奇数的旅行家 Oddytrip 先生计划通过航班从一个机场前往另一个机场。假设他乘坐了 $k$ 次航班：先从机场 $p_1$ 飞往 $p_2$，然后从 $p_2$ 飞往 $p_3$，接着从 $p_3$ 飞往 $p_4$，依此类推，最后从 $p_k$ 飞往 $p_{k+1}$。这个以 $p_1$ 开始、以 $p_{k+1}$ 结束的旅行计划记为 $p_1 \rightarrow p_2 \rightarrow p_3 \rightarrow p_4 \rightarrow \cdots \rightarrow p_k \rightarrow p_{k+1}$。根据他的审美，一个旅行计划是**美丽的**，当且仅当 $n$ 个机场中的每一个在该旅行计划中出现的次数都是奇数。例如，若 $n = 6$，旅行计划 $3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 1 \rightarrow 2$ 和 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 6$ 是美丽的，而 $1 \rightarrow 3 \rightarrow 6$ 和 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 5 \rightarrow 6$ 则不是。特别地，在一个美丽的旅行计划中，每个机场至少出现一次。 初始时，有 $m$ 条航线。随后，你将收到 $q$ 个查询，需要按照给定的顺序处理。每个查询是以下两种类型之一： - $1 \ x \ y$：连接机场 $x$ 和 $y$ 的航线的存在状态发生改变。如果机场 $x$ 和 $y$ 之间已经存在一条航线，则该航线被废除。换句话说，Oddytrip 先生不能再乘坐机场 $x$ 和 $y$ 之间的直达航班（直到它被重新建立）。另一方面，如果之前不存在这样的航线，则在机场 $x$ 和 $y$ 之间新建立一条航线。换句话说，Oddytrip 先生可以乘坐机场 $x$ 和 $y$ 之间的直达航班（直到它被再次废除）。 - $2 \ x \ y$：你需要判断，在此时可用的航线下，是否存在一个以机场 $x$ 开始、以机场 $y$ 结束的美丽旅行计划。

输入包含一个单独的测试用例，格式如下： $$ \begin{aligned} &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 \end{aligned} $$ 第一行包含三个整数 $n$、$m$ 和 $q$（$2 \leq n \leq 100,000$，$0 \leq m \leq 100,000$，$1 \leq q \leq 100,000$），其中 $n$ 是 JAG 国的机场数量，$m$ 是初始可用的航线数量，$q$ 是查询的数量。 接下来的 $m$ 行，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i < v_i \leq n$），表示初始时机场 $u_i$ 和 $v_i$ 之间有一条可用航线。保证这 $m$ 条航线互不相同。 接下来的 $q$ 行，第 $j$ 行包含三个整数 $t_j$、$x_j$ 和 $y_j$（$1 \leq t_j \leq 2$，$1 \leq x_j < y_j \leq n$），表示查询的类型以及如上所述的两个机场编号。保证至少有一个查询满足 $t_j = 2$。

对于每个满足 $t_j = 2$ 的查询，如果存在一个以机场 $x$ 开始、以机场 $y$ 结束的美丽旅行计划，则在一行中输出 "Yes"；否则，输出 "No"。

翻译由 DeepSeek V3.2 完成