题面

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$ 张图上都联通。

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