P6665 [Tsinghua Training 2016] Alice and Bob Are Playing a Game Again

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.

**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 $T$ lines. For each line, output who wins when Alice moves first and both Alice and Bob play optimally.

#### 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