题目描述

给定一张包含 $n$ 个顶点、$m$ 条边的无向图，边从 $1$ 到 $m$ 编号。每条边被染成 $k$ 种颜色之一。第 $i$ 条边连接顶点 $v_i$ 和 $u_i$，颜色为 $c_i$。

称一张图是好的，当且仅当可以在图中恰好保留 $n-1$ 条边，使得：

• 保留下来的边构成一张连通图；
• 每种颜色都至少有一条边被保留下来。

现在给出 $q$ 次边颜色修改。每次修改由两个数 $e_i,w_i$ 描述，表示第 $e_i$ 条边的颜色变为 $w_i$。每次修改后，判断当前图是否是好的。

输入格式

第一行包含三个整数 $n,m,k$（$2 \le n \le 100000$，$1 \le m \le 100000$，$1 \le k \le 8$），分别表示顶点数、边数和颜色数。

接下来 $m$ 行，每行包含三个整数 $v_i,u_i,c_i$（$1 \le v_i,u_i \le n$，$1 \le c_i \le k$，$v_i \ne u_i$），表示第 $i$ 条边的两个端点和颜色。

接下来一行包含一个整数 $q$（$1 \le q \le 100000$），表示修改次数。

接下来 $q$ 行，每行包含两个整数 $e_i,w_i$（$1 \le e_i \le m$，$1 \le w_i \le k$），表示把第 $e_i$ 条边的颜色改为 $w_i$。

保证图中没有自环和重边。

输出格式

对于第 $i$ 次修改后的图，如果它是好的，输出 Yes；否则输出 No。

样例 #1

样例输入 #1

5 5 3
3 4 1
1 5 2
3 2 3
1 4 3
3 5 3
5
1 3
4 1
5 1
2 1
3 2

样例输出 #1

No
Yes
Yes
No
Yes

样例 #2

样例输入 #2

2 1 1
1 2 1
1
1 1

样例输出 #2

Yes

样例解释

第一个样例中，第一次修改后图如下。

此处应插入原题图：第一次修改后的彩色图。

此时没有颜色 $1$ 的边，所以不可能满足题目条件。

第二次修改后图如下。

此处应插入原题图：第二次修改后的彩色图，原图中用红色标出了可以保留的边。

图中可以保留若干原题图中标红的边。这些边包含所有颜色 $1,2,3$，并且构成连通图，因此当前图是好的。

评分方式

测试数据包含 8 个测试组。只有通过该组以及若干指定的前置测试组，才能获得该组分数。Offline-testing 表示该组结果只会在比赛结束后公布。