UOJ Logo

NOI.AC

3S 512MB

#16. T3

统计

小w和小y互相暗恋了对方两年,本可以一直在一起,但是无奈命运和时机都一一错过,留下的只有一片回忆。

在小w的梦里,他和小y一起玩一场直到永远的游戏。游戏规则如下:

游戏的棋盘是一个梦幻的国度,这个国度有$n$座城池,每个城池不是归小w所有,就是归小y所有,城池和城池之间用$m$条有向边连接。

现在有一个遗失的记忆碎片降临到了城市$s$。每当碎片来到一座城市的时候,城市的主人就选择一条出边,把碎片沿着出边移动到对应的城市。保证每个城市至少有一个出边,不能不选。

小w和小y无穷无尽地玩着这个游戏。每个城池有一个属性$p_i$,碎片的移动轨迹上所有城池的$p_i$形成了一条无限长的属性数列。

现在如果数列的上极限是偶数,那么小w就取得了胜利,如果数列的上极限是奇数,那么小y就取得了胜利。

通俗来说,所谓的上极限,就是数列里最大的出现了无穷多次的数字。

输入格式

第一行一个$T$,表示数据组数。

每组数据第一行两个整数$n, m$。

接下来$n$行,每行一个整数$x_i, p_i$.

$x_i = 0$表示这是小w的城池,反之$x_i = 1$则是小y的。$p_i$表示第$i$个城池的属性。

接下来$m$行,每行两个整数$a_i, b_i$。表示一条从$a_i$到$b_i$的有向边。

输出格式

$T$行,每行$n$个字符,表示每个点出发谁获胜,"w"表示小w获胜,"y"表示小y获胜。

样例一

input

3
2 2
1 1
0 2
1 2
2 1
5 7
0 2
1 2
1 4
0 5
0 2
2 1
1 2
4 1
2 4
1 3
3 2
5 5
4 6
1 2
0 2
1 4
0 5
2 1
1 2
4 1
2 4
1 3
3 2

output

ww
yyyyw
wwww

数据范围

时间限制3s,空间限制512MB

$T \leq 5$

测试点编号 $n, p_i$的规模
1,2$n \leq 10, 1 \leq p_i \leq 7, m \leq n^2$
3,4$n \leq 20, 1 \leq p_i \leq 7, m \leq n^2$
5,6$n \leq 28, 1 \leq p_i \leq 7, m \leq n^2$
7,8,9,10$n \leq 50, 1 \leq p_i \leq 7, m \leq n^2$