[Solution] Tree and Permutation Game solution codeforces

Tree and Permutation Game solution codeforces – There is a tree of 𝑛n vertices and a permutation 𝑝p of size 𝑛n. A token is present on vertex 𝑥x of the tree.

[Solution] Tree and Permutation Game solution codeforces

Alice and Bob are playing a game. Alice is in control of the permutation 𝑝p, and Bob is in control of the token on the tree. In Alice’s turn, she must pick two distinct numbers 𝑢u and 𝑣v (not positions; 𝑢𝑣u≠v), such that the token is neither at vertex 𝑢u nor vertex 𝑣v on the tree, and swap their positions in the permutation 𝑝p. In Bob’s turn, he must move the token to an adjacent vertex from the one it is currently on.

Alice wants to sort the permutation in increasing order. Bob wants to prevent that. Alice wins if the permutation is sorted in increasing order at the beginning or end of her turn. Bob wins if he can make the game go on for an infinite number of moves (which means that Alice is never able to get a sorted permutation). Both players play optimally. Alice makes the first move.

Given the tree, the permutation 𝑝p, and the vertex 𝑥x on which the token initially is, find the winner of the game.

Input

The first line contains a single integer 𝑡t (1𝑡10001≤t≤1000)  — the number of test cases. The description of each test case follows.

The first line of each test case has two integers 𝑛n and 𝑥x (3𝑛21053≤n≤2⋅1051𝑥𝑛1≤x≤n).

[Solution] Tree and Permutation Game solution codeforces

Each of the next 𝑛1n−1 lines contains two integers 𝑎a and 𝑏b (1𝑎,𝑏𝑛1≤a,b≤n𝑎𝑏a≠b) indicating an undirected edge between vertex 𝑎a and vertex 𝑏b. It is guaranteed that the given edges form a tree.

The next line contains 𝑛n integers 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn (1𝑝𝑖𝑛1≤pi≤n)  — the permutation 𝑝p.

The sum of 𝑛n over all test cases does not exceed 21052⋅105.

Output

For each test case, output one line containing Alice or Bob — the winner of the game. The output is case-sensitive.

Examples
input

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

[Solution] Tree and Permutation Game solution codeforces

output

Copy
Alice
Bob
Alice
input

Copy
1
11 4
3 11
5 9
10 3
4 8
2 4
1 8
6 8
8 7
4 5
5 11
7 4 9 8 6 5 11 10 2 3 1
output

Copy
Alice
Note

Here is the explanation for the first example:

In the first test case, there is a way for Alice to win. Here is a possible sequence of moves:

  1. Alice swaps 55 and 66, resulting in [2,1,3,5,4,6][2,1,3,5,4,6].
  2. Bob moves the token to vertex 55.
  3. Alice swaps 11 and 22, resulting in [1,2,3,5,4,6][1,2,3,5,4,6].
  4. Bob moves the token to vertex 33.
  5. Alice swaps 44 and 55, resulting in [1,2,3,4,5,6][1,2,3,4,5,6], and wins.

In the second test case, Alice cannot win since Bob can make the game go on forever. Here is the sequence of moves:

  1. Alice can only swap 11 and 33, resulting in [3,1,2][3,1,2].
  2. Bob moves the token to vertex 11.
  3. Alice can only swap 22 and 33, resulting in [2,1,3][2,1,3].
  4. Bob moves the token to vertex 22.
  5. Alice can only swap 11 and 33, resulting in [2,3,1][2,3,1].
  6. Bob moves the token to vertex 33.
  7. Alice can only swap 11 and 22, resulting in [1,3,2][1,3,2].
  8. Bob moves the token to vertex 22.

And then the sequence repeats forever.In the fourth test case, Alice wins immediately since the permutation is already sorted.

For Solution

Click here

Leave a Comment