Description

Alice and Bob are playing a game.

There are $n$ nodes and $m$ edges $(0\le m\le n-1)$, forming several rooted trees. For each tree, the root is the node with the smallest index in that connected component. Alice and Bob take turns to move. In each round, a player chooses an undeleted node $x$ and deletes $x$ and all of its ancestors. The player who cannot make a move loses.

Note: The shape of the trees is fixed at the beginning. Deleting nodes does not change the parent-child relationships among the remaining nodes. For example, for a chain like $1-3-2$, node $1$ is the root. After deleting node $1$, node $3$ is still the parent of node $2$.

Determine whether the first player has a winning strategy.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$, meaning there are $T$ test cases in this test point; then follow $T$ test cases.

For each test case:

The first line contains two integers $n, m$, representing the number of nodes and edges (nodes are numbered starting from $1$).

The next $m$ lines each contain two positive integers $a, b$, indicating there is an edge between node $a$ and node $b. There are no multiple edges in the input.

Output Format

Output $T$ lines. For each line, output who wins when Alice moves first and both Alice and Bob play optimally.

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

Alice
Alice
Bob
Alice

Hint

Sample Explanation

In the first test case, the input is a chain, and Alice can delete all nodes in one move.

In the second test case, Alice can win by deleting node $1$ on the first move.

Constraints

For $100\%$ of the data, $1≤T≤10$, $1≤n≤10^5$, $∑n≤2×10^5$, $0≤m≤n−1$. The input guarantees there is no cycle, and the size of each tree is $≤5×10^4$.

Translated by ChatGPT 5