题目描述

小 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≠v$。

我们认为一个点对 $(u,v)$ 联通意味着 $u$ 可以通过图上的一些边抵达 $v$，同样的 $v$ 可以通过图上的一些边抵达 $u$。

调皮的小 F 难倒了小 T，你能编写程序帮帮小 T 吗？

输入格式

第一行输入一个正整数 $T$ ($1≤T≤5$)，表示总共有 $T$ 组数据。

对于每一组测试数据，首先读入四个整数 $n,m,d,k$ ($1≤n≤5×10^4, 0≤m≤10^5, 0≤d≤100, 1≤k≤10^5$)，分别表示小 T 初始所拥有的图的点数，边数，小 F 复制次数，以及小 F 总共加的边数。具体含义同题目描述中一致。

接下来 $m$ 行，每一行读入两个正整数 $u,v$ 表示小 T 初始所拥有的图中有一条无向边 $(u,v)$。

接下来 $k$ 行，每一行读入三个正整数 $u,v,w$ ($1≤u,v≤n, 1≤w≤d+1$)，表示这次小 F 会用一条无向边连接第 $w$ 张图上的 $u,v$ 两点。

注意: 连接的边中可能会出现重边或自环。

输出格式

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

输入样例

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

输出样例

1
1
1
1
1
1
3
3