文理学院程序设计在线练习


灾后重建

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 67   Accepted Submission(s): 28
Problem Description

作为最具破坏力的自然灾害之一,地震所带来的危害是人们不愿看到的。

然而,百年一遇的地震还是发生了,不少道路受毁而导致中断,只剩下少量的道路还保持连通。地震后的灾区满目疮痍,百废待兴,甚至有些地区因道路中断而与外界隔绝。

已知灾区原有N个城市,编号分别为1~N,其中首都编号为1。假设地震后还剩下M条道路尚可使用。

灾后重建的首要任务之一就是修建道路,在道路建设者的努力下,道路成功修建的Q条消息接连传来。
现在请你依次在收到每条消息后,分别作出计算,计算该时刻分别还有多少城市和多少人口尚未与首都取得连通。(此处忽略地震所造成的人员死亡数量)

Input

输入数据首先包含一个整数T,表示测试实例的个数,然后是T组测试数据。(1<=T<=30)
对于每组测试数据,第一行是3个正整数N,M,Q,(2<=N<=500, 0<=M<=500,1<=Q<=500),分别表示城市数量N,地震后尚可使用的道路数量M,以及重建道路的信息数量Q.
第二行有N个整数,分别表示N个城市的人口数量(万)。
接下来有M行数据,分别表示地震后尚可使用的M条道路的信息,每行2个整数a,b,表示城市a,b之间的道路仍可使用。
再接下来有Q行数据,分别表示道路成功修建的Q条消息,每行2个整数c,d,表示城市c,d之间的道路已经修复。

Output

对于每组测试的每条成功修建的消息,分别计算此时还有多少城市和多少(万)人口尚未与首都取得连通。城市数和人口数之间用空格分隔,每组信息一行。输出格式请参考Sample Output.

Sample Input
3
3 0 1
800 300 200
3 1
5 1 3
800 300 200 500 400
1 2
3 4
1 3
2 3
4 2 2
4 3 2 1
1 2
1 3
2 3
1 4
Sample Output
1 300
3 1100
1 400
1 400
1 1
0 0
Author

flx

Source

绍兴文理学院第五届程序设计竞赛2011/03/27