4116. [统一省选 2025]追忆

【题目背景】

【题目描述】

给定一个 $n$ 个点 $m$ 条边的有向图 $G$，结点由 $1$ 至 $n$ 编号。第 $i$ ($1 \leq i \leq m$) 条边从 $u_i$ 指向 $v_i$，保证 $u_i < v_i$。节点 $j$ ($1 \leq j \leq n$) 有两个权值 $a_j, b_j$，保证 $[a_1, \ldots, a_n]$ 与 $[b_1, \ldots, b_n]$ 均是 $1 \sim n$ 的排列。 你需要进行 $q$ 次操作。操作有以下三种:

 - $1\ x\ y$：交换 $a_x$ 和 $a_y$； 

 - $2\ x\ y$：交换 $b_x$ 和 $b_y$；

 - $3\ x\ l\ r$：你需要输出满足以下两个条件的点 $y$ 中 $b_y$ 的最大值，若不存在满足条件的点则输出 $0$：

    1.$l \leq a_y \leq r$。

    2.图 $G$ 中存在一条 $x$ 到 $y$ 的有向路径，即存在整数 $k \geq 1$ 与 $k$ 个结点 $p_1, p_2, \ldots, p_k$，

     满足$p_1 = x$，$p_k = y$，且对于所有 $1 \leq i < k$，图 $G$ 中存在从 $p_i$ 指向 $p_{i+1}$ 的有向边。

      特别地，图 $G$ 中总是存在一条 $x$ 到 $x$ 的有向路径。

【输入格式】

本题有多组测试数据。

输入的第一行两个整数 $c, T$，分别表示测试点编号和测试数据组数，接下来输入每组测试数据。

样例满足 $c = 0$。 对于每组测试数据，

 - 第一行三个整数 $n, m, q$，分别表示图 $G$ 的节点数、图 $G$ 的边数和操作次数，

 - 接下来 $m$ 行，第 $i$ ($1 \leq i \leq m$) 行两个整数 $u_i, v_i$，描述一条边，

 - 接下来一行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，描述每个节点的 $a$ 权值，

 - 接下来一行 $n$ 个整数 $b_1, b_2, \ldots, b_n$，描述每个节点的 $b$ 权值，

 - 最后 $q$ 行，第 $i$ ($1 \leq i \leq q$) 行三或四个整数 $o_i, x_i, y_i$ 或 $o_i, x_i, l_i, r_i$，描述一次操作，格式同题目描述。

【输出格式】

对于每个 $3$ 操作输出一行一个整数，表示对应操作的答案。

【样例输入】

0 1
4 4 7
1 2
1 3
2 4
3 4
4 2 3 1
1 3 2 4
3 2 1 3
3 3 2 4
1 1 4
3 1 1 3
2 2 4
3 1 2 3
3 4 1 1

【样例输出】

4
2
3
4
0

【样例说明】

该组样例共有 $1$ 组测试数据。该组测试数据共包含 $7$ 个操作。

- 对于第一个操作，所有满足条件的点为 $2, 4$，因此答案为 $\max\{b_2, b_4\} = 4$。

- 对于第二个操作，所有满足条件的点为 $3$，因此答案为 $b_3 = 2$。

- 对于第三个操作，交换 $a_1, a_4$ 后得到的权值序列 $a$ 为 $[1, 2, 3, 4]$。

- 对于第四个操作，所有满足条件的点为 $1, 2, 3$，因此答案为 $\max\{b_1, b_2, b_3\} = 3$。

- 对于第五个操作，交换 $b_2, b_4$ 后得到的权值序列 $b$ 为 $[1, 4, 2, 3]$。

- 对于第六个操作，所有满足条件的点为 $2, 3$，因此答案为 $\max\{b_2, b_3\} = 4$。

- 对于第七个操作，没有满足条件的点，因此答案为 $0$。

【数据规模与约定】

【来源】

2025联合省选day1T2