問題文

Alice と Bob がグラフ上のケイドロで遊ぼうとしています。

グラフ上のケイドロでは、ターン制で以下のいずれかの行動を交互に行います。

• 今いる頂点から、隣接頂点へ移動する。
• パスする。（今いる頂点に留まる。）

Alice が行動を行った直後に Alice と Bob が同じ頂点にいるとき、Alice は Bob を捕まえることができます。

Alice と Bob が遊ぶ N 頂点 N 辺の単純無向連結グラフが与えられます。 i 番目の辺は頂点 u_i と頂点 v_i を結んでいます。

Alice と Bob がそれぞれ頂点 a, b にいる状態で、Alice のターンから始めます。 有限ターン内に Alice が Bob を必ず捕まえられるか判定してください。 ただし、 Alice と Bob は互いに相手の位置を知っており、 Alice は Bob をできる限り捕まえようと、 Bob は Alice にできる限り捕まらないように行動するものとします。

制約

• 3 \le N \le 2\times 10^5
• 1 \le u_i,v_i \le N
• 1 \le a,b \le N
• a \neq b
• 与えられるグラフは単純である。すなわち、自己ループや多重辺は存在しない。
• 与えられるグラフは連結である。
• 入力はすべて整数。

入力例 1

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

出力例 1

Alice

たとえば以下の進行が考えられます。

• Alice がパスする。
• Bob が頂点 5 に移動する。
• Alice が頂点 6 に移動し、Bob を捕まえる。

この進行はあくまで一例ですが、この入力例では Alice が有限ターン内で Bob を必ず捕まえられることが証明できます。

入力例 2

4 1 2
1 2
1 4
2 3
3 4

出力例 2

Alice

入力例 3

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

出力例 3

Bob