题目描述
小 G 有一张有向无环图,n 个点 m 条边。每个点有点权,初始均为 0。你需要帮助她
完成 q 次操作:
- 操作 1,给出 u 和 x,把所有 u 可以到达的点的点权设为 x
- 操作 2,给出 u 和 x,把所有 u 可以到达的点的点权与 x 取 min
- 操作 3,给出 u,询问 u 的点权
输入格式
第一行,三个正整数 n, m, q
接下来 m 行,每行两个正整数 u 和 v,表示一条从 u 到 v 的有向边
接下来 q 行,每行一个操作,为 1 u x、2 u x 和 3 u 之一
输出格式
对于所有询问操作,依次输出答案
数据范围
对于 20% 的数据,1 ≤ n, m, w ≤ 5000
对于另外 10% 的数据,没有 1 操作
对于另外 10% 的数据,没有 2 操作,1 ≤ n, m, q ≤ 50000
对于另外 20% 的数据,没有 2 操作
对于另外 20% 的数据,1 ≤ n, m, q ≤ 50000
对于 100% 的数据,1 ≤ n, m, q ≤ 10^5,点的编号从 1 到 n,且 0 ≤ x ≤ 10^9