图计算

Problem Description

小 T 有一个 $n$ 个点 $m$ 条边的无向图，在这个图上他能够很轻易地计算有多少个点对互相联通。 有一天，调皮的小 F 将这张图复制了 $d$ 次，也就是总共有 $d+1$ 张图，每一张图初始都与小 T 原来持有的图相同。 小 F 为了难倒小 T，他还会偷偷往这些图里面加总共 $k$ 条边。小 F 的每次加边操作会给定 $(u, v, w)$ 表示用一条无向边连接第 $w$ 张图上的 $(u,v)$ 点对。每次操作后小 F 还是会问小 T 有多少个无序点对 $(u,v)$ 满足 $u,v$ 在 $d+1$ 张图上都联通，且 $u\neq v$。 我们认为一个点对 $(u,v)$ 联通意味着 $u$ 可以通过图上的一些边抵达 $v$，同样的 $v$ 可以通过图上的一些边抵达 $u$。 调皮的小 F 难倒了小 T，你能编写程序帮帮小 T 吗？

Input

第一行输入一个正整数 $T$ ($1\le T\le 5$)，表示总共有 $T$ 组数据。 对于每一组测试数据，首先读入四个整数 $n,m,d,k$ ($1\le n \le 5\times 10^4$, $0\le m \le 10^5$, $0\le d \le 100$, $1\le k \le 10^5$)， 分别表示小 T 初始所拥有的图的点数，边数，小 F 复制次数，以及小 F 总共加的边数。具体含义同题目描述中一致。 接下来 $m$ 行，每一行读入两个正整数 $u,v$ 表示小 T 初始所拥有的图中有一条无向边 $(u,v)$。 接下来 $k$ 行，每一行读入三个正整数 $u,v,w$ ($1\le u,v \le n$, $1\le w \le d+1$)，表示这次小 F 会用一条无向边连接第 $w$ 张图上的 $u,v$ 两点。 注意: 连接的边中可能会出现重边或自环。

Output

对于每一组测试数据，总共输出 $k$ 行，每行一个整数表示小 F 加入当前这条无向边之后，有多少个无序点对 $(u,v)$ 满足 $u,v$ 在 $d+1$ 张图上都联通。

Sample Input

1
3 1 3 8
1 2
1 3 1
1 3 2
1 3 3
2 3 1
2 3 2
2 3 3
1 3 4
2 3 4

Sample Output

1
1
1
1
1
1
3
3

Source

2024“钉耙编程”中国大学生算法设计超级联赛（2）