[ZJOI2012]网络

题目描述

有一个无向图 $G$,每个点有个权值,每条边有一个颜色。这个无向图满足以下两个条件: 1、 对于任意节点连出去的边中,相同颜色的边不超过两条。 2、图中不存在同色的环,同色的环指相同颜色的边构成的环。 在这个图上,你要支持以下三种操作: - `0 x y` 表示把节点 $x$ 的权值改为 $y$ - `1 u v w` 表示将边 $(u,v)$ 的颜色改为 $w$。 - `2 c u v` 表示查询由颜色 $c$ 的边构成的图中,所有可能在 $u \to v$ 之间的简单路径上的节点的权值的最大值。

输入输出格式

输入格式


第一行四个正整数 $n,m,C,k$,分别表示节点数、边数、颜色数和操作数。 接下来 $n$ 行,每行一个正整数 $v_i$,为节点 $i$ 的权值。 之后 $m$ 行,每行三个正整数 $u,v,w$,为一条连接 $u,v$ 节点的边,颜色为$w$。 最后 $k$ 行,每行若干个正整数,表示一次操作。

输出格式


输出若干行,每行输出一个对应的信息。 1、 对于修改节点权值操作,不需要输出信息。 2、对于修改边的颜色操作,按以下几类输出: - 若不存在连接节点 $u$ 和节点 $v$ 的边,输出 `No such edge.`。 - 若修改后不满足条件 $1$,不修改边的颜色,并输出 `Error 1.`。 - 若修改后不满足条件 $2$,不修改边的颜色,并输出 `Error 2.`。 - 其他情况,成功修改边的颜色,并输出 `Success.`。 输出满足条件的第一条信息即可,即若同时不满足条件 $1,2$ ,则只需要输出`Error 1.`。 3、 对于查询操作,输出一个整数表示答案。若 $u,v$ 之间没有颜色 $c$ 构成的路径,则输出 $-1$。

输入输出样例

输入样例 #1

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

输出样例 #1

4
Success.
Error 2.
-1
Error 1.
5

说明

![](https://cdn.luogu.com.cn/upload/pic/1714.png) 颜色 $0$ 为实线的边,颜色 $1$ 为虚线的边, 由颜色 $0$ 构成的从节点 $1$ 到节点 $4$ 的路径有 $1 \to 2 \to 4$,故$\max\{v_1, v_2, v_4\} = \max\{ 1, 2, 4 \} = 4$。 将连接节点 $1$ 和节点 $2$ 的边修改为颜色 $1$,修改成功,输出 `Success.` 将连接节点 $4$ 和节点 $3$ 的边修改为颜色 $1$,由于修改后会使得存在由颜色 $1$ 构成的环( $1 – 2 – 4 – 3 – 1$ ),不满足条件 $2$,故不修改,并输`Error 2`。 不存在颜色 $0$ 构成的从节点 $1$ 到节点 $4$ 的边,输出 `-1`。 将连接节点 $2$ 和节点 $3$ 的边修改为颜色 $1$,由于修改后节点 $2$ 的连出去的颜色为 $1$ 的边有 $3$ 条,故不满足条件 $1$,故不修改,并输出`Error 1.` 。 将节点 $2$ 的权值修改为 $5$。 由颜色 $1$ 构成的从节点 $1$ 到节点 $4$ 的路径有 $1 \to 2 \to 4$,故$\max\{v_1, v_2, v_4\} = \max\{ 1, 5, 4 \} = 5$。 【数据范围】 对于 $30\%$ 的数据:$n ≤ 1000$,$m ≤ 10^4$,$k ≤ 1000$; 另有 $20\%$ 的数据:$n ≤ 10^4$,$m ≤ 10^5$,$C = 1$,$k ≤ 10^5$; 对于 $100\%$ 的数据:$n ≤ 10^4$,$m ≤ 10^5$,$C ≤ 10$,$k ≤ 10^5$。 $1\le u,v,x \le n$,$0 \le c < C$,保证图中没有重边和自环。