化学题1

$NoWa$ 有许多玻璃瓶，他将它们放置在一个水平面上，并用管子将它们的顶部连接起来。$NoWa$ 在连接全部完成后，会执行 $q$ 次操作，每次操作会向瓶子 $a$ 里加不断地加入饱和食盐溶液，然后在 $t$ 秒后对所有瓶子加热蒸干（加热时间忽略不计）。如果在加热蒸干时，瓶子内有水，那么该瓶会收获一单位的食盐。

加热前，盐水会随着时间通过管子逐渐向外流动，盐水充满瓶子不需要时间，但是水通过一根管子需要 $1$ 秒。

每次操作都会在上一次操作结束后进行。请在所有操作完成后输出每个瓶子收获的食盐总量。

样例说明：

对于第一组样例：
瓶子的连接图为：


第一次操作：向瓶子1里加水，2s后蒸干；此时，瓶子1,2,3,4内各获得一份食盐。

第二次操作：向瓶子2内加水，1s后蒸干；此时，瓶子1,2,3内获得一份食盐，由于瓶子2到瓶子4的最短路径为2->1->4，需要2秒，所以蒸干装置时瓶子4内没有水，不能获得食盐。

最终各瓶子获得食盐数量分别为2,2,2,1。

第一行一个整数 $T(1 \leq T \leq 30)$ ，表示测试数据组数，接下来包含 $T$ 组测试数据。

对于每组测试数据，输入三个整数 $n,m,q\ (2 \leq n \leq 10^4,1 \leq m \leq 5 \times 10^4,1 \leq q \leq 10^3)$ 。

接下来输入 $m$ 行，每行两个整数 $u,v\ (1 \leq u,v \leq n)$ 且 $u \neq v$ ，表示将 $u$ 和 $v$ 连接。

接下来输入 $q$ 行，每行两个整数 $a,t\ (1 \leq a \leq n,1 \leq t \leq 10^3)$ 。

对于每组测试数据，输出 $n$ 个数，第 $i$ 个数表示第 $i$ 个瓶子收获的食盐总量。

请不要输出行末空格。

2
4 4 2
1 2
1 3
1 4
2 3
1 2
2 1
6 7 3
2 1
2 4
2 6
1 6
4 5
3 6
5 3
3 10000
6 1
1 2

2 2 2 1 
3 3 3 2 1 3

杭州电子科技大学2020新生编程大赛