题目描述

有一张 $n$ 个点 $m$ 条边的 DAG（有向无环图），每个点有一个点权，初始时都为 $0$，需要支持 $q$ 次如下操作：

操作 $1$：给出 $u,x$，把 DAG 上点 $u$ 能到达的所有点的点权设为 $x$。

操作 $2$：给出 $u,x$，把 DAG 上点 $u$ 能到达的所有点的点权对 $x$ 取$\min$。

操作 $3$：给出 $u$，询问点 $u$ 的点权。

输入格式

输入数据第一行包含三个正整数 $n,m,q$。

接下来 $m$ 行，每行两个整数 $u,v$ 表示一条从 $u$ 到 $v$ 的有向边。

接下来 $q$ 行，每行格式为以下三者其一：

$1\ u\ x$表示把 DAG 上点 $u$ 能到达的所有点的点权设为 $x$。

$2\ u\ x$表示把 DAG 上点 $u$ 能到达的所有点的点权对 $x$ 取 $\min$。

$3\ u$表示询问点 $u$ 的点权。

输出格式

对于每次询问操作，输出一行一个整数表示询问的答案。

6 5 12
1 2
1 3
3 4
2 4
5 6
1 1 3
3 1
3 2
1 2 2
3 3
3 4
2 6 7
3 5
3 6
2 1 3
3 2
3 3

3
3
3
2
0
0
2
3

数据范围

对于 $20\%$ 的数据，$1 \le n, m, q \le 5000$；

对于另外 $10\%$ 的数据，没有 $1$ 操作；

对于另外 $10\%$ 的数据，没有 $2$ 操作且 $1 \le n, m, q \le 50000$；

对于另外 $20\%$ 的数据，没有 $2$ 操作；

对于另外 $20\%$ 的数据，$1 \le n, m, q \le 50000$；

对于 $100\%$ 的数据，$1 \le n, m, q \le 10^5, 1 \le u \le n, 0 \le x \le 10^9$。

大样例

大样例下载