Problem Description

Given a deterministic finite automaton (DFA) with state set $Q=\{1,2,\dots,n\}$, start state $q=1$, accepting state set $F$ of size $m$, and alphabet $\Sigma=\{\texttt{A},\texttt{C}\}$. Compute the lexicographically smallest string that can be accepted by the automaton and has length at least $k$. Since the answer may be very long, if the length of the answer exceeds $n$, you only need to output the last $n$ characters of the answer. If no string satisfying the above requirements exists, output WA.

A string is accepted by the automaton if and only if there exists a walk that starts from the start state and ends at an accepting state, such that the letters on the transition edges traversed form exactly the string. The walk may visit repeated states and repeated edges.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$ ($1\le T\le 5\times 10^5$), indicating the number of test cases.

For each test case:

• The first line contains three integers separated by spaces: the number of states $n$ ($2\le n\le 10^6$), the number of accepting states $m$ ($1\le m\le n-1$), and the minimum length $k$ ($1\le k\le 10^9$).
• The second line contains $m$ integers separated by spaces, indicating the accepting state set. It is guaranteed that these numbers are all in $[2,n]` and are distinct.
• The next $n$ lines each contain $2$ integers separated by spaces. In line $i$, the two integers represent the state reached from state $i$ by transitions labeled A and C, respectively.

It is guaranteed that $\sum n\le 10^6$.

Output Format

Output $T$ lines. Each line outputs one string, where the $i$-th line is the answer for the $i$-th test case.

2
5 1 6
4
2 5
5 3
4 2
5 5
5 5
3 1 2
2
2 3
3 3
3 3

CCCCA
WA

Hint

In the first sample test case, the language recognized by the DFA is $\{\texttt{A}\texttt{C}^{2t+1}\texttt{A}\mid t\ge 0\}$.

Translated by ChatGPT 5