AT_abc427_d [ABC427D] The Simple Game

There is a directed graph with $ N $ vertices and $ M $ edges. The vertices are numbered from $ 1 $ to $ N $ , and the $ i $ -th edge is a directed edge from vertex $ U_i $ to vertex $ V_i $ . Here, the out-degree of each vertex is at least $ 1 $ . Also, each vertex has a character written on it, and the character written on vertex $ i $ is $ S_i $ . Here, $ S_i $ refers to the $ i $ -th character of $ S $ . Alice and Bob play the following game on this graph using one piece: - Initially, the piece is placed on vertex $ 1 $ , and they alternately perform the following operation $ K $ times each, with Alice going first and Bob going second. - Let $ u $ be the vertex where the piece is currently placed. Choose a vertex $ v $ such that there is an edge from vertex $ u $ to vertex $ v $ , and move the piece to vertex $ v $ . - Let $ v $ be the vertex where the piece is finally placed. If $ S_v = $ `A`, Alice wins; if $ S_v = $ `B`, Bob wins. Find the winner of the game when both players play optimally. In each input, you are given $ T $ test cases. Solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \ldots $ $ \text{case}_T $ Here, $ \text{case}_i $ represents the $ i $ -th test case, and each test case is given in the following format: > $ N $ $ M $ $ K $ $ S $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $ \vdots $ $ U_M $ $ V_M $

Print $ T $ lines. The $ i $ -th line should contain `Alice` if Alice wins when both players play optimally in the $ i $ -th test case, and `Bob` if Bob wins.

### Sample Explanation 1 We will explain an example of how the game proceeds in the first test case. Here, both players do not necessarily play optimally. - Initially, the piece is placed on vertex $ 1 $ . - Alice moves the piece to vertex $ 2 $ . - Bob moves the piece to vertex $ 3 $ . - Alice moves the piece to vertex $ 3 $ . - Bob moves the piece to vertex $ 1 $ . At this point, $ S_1 = $ `A`, so Alice wins. ### Constraints - $ 1 \leq T $ - $ 2 \leq N, M \leq 2 \times 10^5 $ - $ 1 \leq K \leq 10 $ - $ S $ is a string of length $ N $ consisting of `A` and `B`. - $ 1 \leq U_i, V_i \leq N $ - $ (U_i, V_i) \neq (U_j, V_j) $ if $ i \neq j $ . - The out-degree of each vertex is at least $ 1 $ . - The sum of $ N $ over all test cases in a single input is at most $ 2 \times 10^5 $ . - The sum of $ M $ over all test cases in a single input is at most $ 2 \times 10^5 $ .