AT_abc427_d [ABC427D] The Simple Game

$ N $ 頂点 $ M $ 辺の有向グラフがあります。頂点には $ 1 $ から $ N $ までの番号が付けられており、 $ i $ 番目の辺は頂点 $ U_i $ から頂点 $ V_i $ へ向かう有向辺です。ここで、各頂点の出次数は $ 1 $ 以上です。 また、各頂点には文字が書かれており、頂点 $ i $ に書かれている文字は $ S_i $ です。ただし、 $ S_i $ とは $ S $ の $ i $ 文字目を指します。 Alice と Bob はこのグラフ上で $ 1 $ つの駒を用いて以下のゲームを行います。 - はじめ、駒は頂点 $ 1 $ に置かれており、Alice が先手、Bob が後手となって以下の操作を交互に $ K $ 回ずつ行う。 - 現在駒が置かれている頂点を $ u $ とする。頂点 $ u $ から頂点 $ v $ に向かう辺が存在するような頂点 $ v $ を選び、駒を頂点 $ v $ に移動させる。 - 最終的に駒が置かれている頂点を $ v $ として、 $ S_v = $ `A` のとき Alice の勝ち、 $ S_v = $ `B` のとき Bob の勝ちである。 両者が最適に行動したときのゲームの勝者を求めてください。 $ 1 $ つの入力において $ T $ 個のテストケースが与えられます。それぞれについて答えてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \ldots $ $ \text{case}_T $ ここで、 $ \text{case}_i $ は $ i $ 番目のテストケースを表し、各テストケースは以下の形式で与えられる。 > $ N $ $ M $ $ K $ $ S $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $ \vdots $ $ U_M $ $ V_M $

$ T $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のテストケースにおいて両者が最適に行動したときに Alice が勝つ場合 `Alice` を、Bob が勝つ場合 `Bob` を出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについてゲームの進行の一例を説明します。ただし、この進行において両者は最適に行動しているとは限りません。 - はじめ、駒は頂点 $ 1 $ に置かれている。 - Alice が頂点 $ 2 $ に駒を動かす。 - Bob が頂点 $ 3 $ に駒を動かす。 - Alice が頂点 $ 3 $ に駒を動かす。 - Bob が頂点 $ 1 $ に駒を動かす。 このとき、 $ S_1 = $ `A` であるため Alice の勝ちとなります。 ### Constraints - $ 1 \leq T $ - $ 2 \leq N, M \leq 2 \times 10^5 $ - $ 1 \leq K \leq 10 $ - $ S $ は `A`, `B` からなる長さ $ N $ の文字列 - $ 1 \leq U_i, V_i \leq N $ - $ i \neq j $ のとき $ (U_i, V_i) \neq (U_j, V_j) $ - 各頂点の出次数は $ 1 $ 以上 - $ 1 $ つの入力に含まれるテストケースについて、 $ N $ の総和は $ 2 \times 10^5 $ 以下 - $ 1 $ つの入力に含まれるテストケースについて、 $ M $ の総和は $ 2 \times 10^5 $ 以下