该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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

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