羊村村长选举

慢羊羊已经担任羊村村长很多年了，他决定在今年下任休息，同时推举拜羊羊和川羊羊进行村长的选举竞争。

羊村选举分 $n$ 个部落计票，共有 $k$ 张选票，第 $i$ 个部落有 $a_i$ 张选票，部落内各议员分别投票，票数多的一方将获得该部落的全部选票。

部落之间往往有很多政治意见联系，因此某些部落只有在参考了别的部落选举意见后才会投出选票，例如3号部落希望参考2号和7号的意见，那么当2号和7号部落都投出选票后，3号部落才会投出选票。

选举过程中，每一轮组委会每次都会召集当前所有可以进行投票的部落，拜羊羊和川羊羊要在他们面前进行一次竞选演讲，然后本轮竞选中参与的部落根据该部落的选票意愿投出选票。选举过程中，率先获得至少 $\lceil \frac{k}{2} \rceil +1$ 张选票的羊将直接获胜，选举立即结束，每个部落都投出选票后，选举也立即结束。

其中 $\lceil x \rceil$ 表示 $x$ 向上取整的结果。

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

对于每组测试数据，第一行输入三个整数 $n,m,k\ (1\leq n \leq 1000,0\leq m \leq \frac{n\times (n-1)}{2},n \leq k \leq 10^9)$ ，表示羊村共有 $n$ 个部落，有 $m$ 个限制关系，$n$ 个部落的总选票数量为 $k$ 。

接下来输入一行 $n$ 个整数 $a_i\ (1\leq a_i \leq 10^9,\sum a_i=k)$，表示第 $i$ 个部落有 $a_i$ 张选票。

接下来输入 $m$ 行，每行两个整数 $u,v(1 \leq u,v \leq n,u \neq v)$ ，表示 $u$ 号部落希望参考 $v$ 号部落的意见。

接下来输入 $n$ 行，每行两个整数 $x,y(0\leq x,y \leq 10^9,x \neq y)$，表示对于 $i$ 号部落 ，有 $x$ 票支持拜羊羊，有 $y$ 票支持川羊羊。

保证所有部落都可以投出选票。

对于每组测试数据，输出第一行表示获胜者，如果是拜羊羊获胜，输出 $B$ ，如果是川羊羊获胜，输出 $C$ ，如果产生平局，输出 $BC$ 。

接下来一行输出两个整数 $P,Q$ ，表示选举结束时，有 $P$ 票支持拜羊羊，有 $Q$ 票支持川羊羊。

最后一行输出一个整数 $S$ ，表示选举结束时共进行了 $S$ 轮竞选。

1
5 5 8
1 4 1 1 1
2 1
3 1
4 2
4 3
5 1
1 2
2 1
2 1
10 3
1 3

B
5 2
2

第一轮竞选中，只有1号部落参与，
按照选票意愿，拜羊羊0票，川羊羊获得获得1号部落的1票，本轮比分0:1，总比分0:1。

第二轮竞选中，2号、3号和5号部落参与选举，
按照选票意愿，拜羊羊获得2号部落的4票和3号部落的1票，川羊羊获得5号部落的1票，本轮比分5:1，总比分5:2。

因为拜羊羊率先获得5票，所以直接获得选举胜利，选举结束时总比分为5:2，共进行了2轮竞选。

内蒙古自治区第十五届大学生程序设计竞赛