406034: GYM102220 F Mini-game Before Contest

On the day before this contest, two CCPC teams are playing a game after dress rehearsal.

As we know, a CCPC team consists of $$$3$$$ contestants, so there are $$$6$$$ players in the game. The game is played on a directed graph. The graph has $$$n$$$ vertices and $$$m$$$ arcs. These vertices are labeled by $$$1,2,\dots,n$$$.

Initially, there is a token placed in one of the graph vertices. Players take turns moving the token along one of the arcs that starts in the vertex the token is currently in. When there is no such arc, then this player's team loses the game.

Let's mark two teams as $$$A$$$ and $$$B$$$, then the order of $$$6$$$ players can be displayed as a string $$$ord$$$ with length $$$6$$$. Player from team $$$ord_1$$$ moves first, then $$$ord_2,ord_3,\dots,ord_6,ord_1\dots$$$

Each player will follow a strategy that leads his team to win, and if there is no possible to win, he will try to make the game run infinitely. But some contestants announce they are "actors" before the game, each of them will follow a strategy that leads his team to lose, and if there is no possible to lose, he will try to make the game run infinitely.

All the players know what the order is and who are actors. They also know preferences of other players. They will play optimally, but they are not allowed to discuss before or during the game.

For each initial position of the token, your task is to determine what kind of result the game is going to have.

The first line of the input contains an integer $$$T(1\leq T\leq 100)$$$, denoting the number of test cases.

In each test case, there is two integers $$$n(1\leq n\leq 100000,1\leq m\leq 200000)$$$ in the first line, denoting the number of vertices and arcs.

For the next $$$m$$$ lines, each line contains two integers $$$u_i,v_i(1\leq u_i,v_i\leq n)$$$, denoting an arc from vertex $$$u_i$$$ to vertex $$$v_i$$$. Note that $$$u_i$$$ can be the same with $$$v_i$$$, but no arc will appear more than once.

The next line contains a string $$$ord$$$ of length 6, denoting the order. There are exactly $$$3$$$ of which are "A" and the others are "B".

The next line contains six integers $$$a_1,a_2,\dots,a_6(0\leq a_i\leq 1)$$$, where $$$a_i$$$ denotes whether the player corresponding to $$$ord_i$$$ is an actor. Specifically, $$$a_i=1$$$ means he is an actor while $$$a_i=0$$$ means not.

It is guaranteed that $$$\sum n\leq 2\times 10^6$$$ and $$$\sum m\leq 3\times 10^6$$$.

For each test case, print a single line containing $$$n$$$ characters, where the $$$i$$$-th character should denote the result of the game if the token is in vertex $$$i$$$ initially. The result of the game is denoted by "A" if the team $$$A$$$ wins the game, "B" if the team $$$B$$$ wins the game, and "D" if the game runs infinitely.

2
4 4
1 2
2 3
3 1
1 4
AAABBB
000000
6 6
1 2
2 3
3 1
1 4
2 5
5 6
AAABBB
001000

DADB
ABBBBB