Big Tree Reversing Game

题目描述

You are given a tree with $n$ vertices. Each edge has an initial direction. There is a token initially placed on vertex $1$.

There is also a set $T$ of terminal vertices.

Two players, Alice and Bob, play alternately. Alice moves first.

In one turn, the current player performs the following two operations:

1. choose an edge incident to the vertex containing the token and reverse its direction;
2. choose a directed path starting from the current vertex of the token, such that the endpoint of this path is a vertex whose incident edges are all directed towards it, and then move the token to the endpoint of this path.

If, after both operations of a player's turn are completed, the token is on a vertex in $T$, the game ends.

Alice wants the game to end. Bob wants the game to never end.

Assuming both players play optimally, determine whether Alice can force the game to end from the initial position.

It is guaranteed that every edge incident to vertex $1$ is initially directed towards vertex $1$ and $1 \notin T$.

输入格式

The input contains multiple test cases.

The first line contains an integer $t$ ($1 \le t \le 10^6$), the number of test cases.

For each test case, the first line contains an integer $n$ ($2 \le n \le 10^6$).

The second line contains an integer $k$ ($1 \le k \le n-1$), the number of terminal vertices.

The third line contains $k$ distinct integers $a_1,a_2,\ldots,a_k$ ($2 \le a_i \le n$). These vertices form the terminal set $T=\{a_1,a_2,\ldots,a_k\}$.

Each of the next $n-1$ lines contains two integers $u,v$ ($1 \le u,v \le n$, $u \ne v$), describing an edge initially directed from $u$ to $v$.

The sum of $n$ over all test cases does not exceed $10^6$.

输出格式

For each test case, print one line.

If Alice can force the game to end from the initial position, print Alice. Otherwise, print Bob.

样例输入 #1

4
2
1
2
2 1
3
1
3
2 1
3 2
3
1
2
2 1
2 3
4
1
4
2 1
3 2
3 4

样例输出 #1

Alice
Bob
Alice
Bob