#2073. Alice 和 Bob 又在玩游戏
Alice 和 Bob 又在玩游戏
Alice 和 Bob 又在玩游戏
题目描述
标题: Alice 和 Bob 又在玩游戏 - Problem - QOJ.ac
#4549. Alice 和 Bob 又在玩游戏
The problem was used in the following contests:
Alice 和 Bob 又在玩游戏。
有 n 个节点,m 条边(0≤m≤n−1),构成若干棵有根树,每棵树的根节点是该连通块内编号最小的点。
Alice 和 Bob 轮流操作(Alice 先手),每回合选择一个没有被删除的节点 x,将 x 及其所有祖先全部删除,不能操作的人输。
需要注意的是,树的形态是在一开始就确定好的,删除节点不会影响剩余节点父亲和儿子的关系。
比如:1-3-2 这样一条链,1 号点是根节点,删除 1 号点之后,3 号点还是 2 号点的父节点。
假设 Alice 和 Bob 都足够聪明,问 Alice 有没有必胜策略。
输入格式
第一行一个正整数 T,表示该测试点有 T 组数据;接下来 T 组数据。
对于每组数据:
输入第一行两个整数 n, m,分别表示点数和边数(节点从 1 开始编号)。
接下来 m 行,每行两个正整数 a, b,表示节点 a 和节点 b 之间有一条边,输入数据中没有重边。
输出格式
输出 T 行,每行输出 Alice 先手并且 Alice 和 Bob 都足够聪明的情况下谁获胜。
样例一
input
4
2 1
1 2
3 2
1 2
1 3
2 0
3 1
1 2
output
Alice
Alice
Bob
Alice
explanation
输入共 4 组数据;
第一组数据输入是一条链,Alice 可以一次性把所有节点都删掉。
第二组数据,Alice 先手第一步删除 1 号点即可胜利。
样例二
见下发文件。
样例三
见下发文件。
限制与约定
对于10%的数据,m=0;
对于20%的数据,1≤n≤20;
对于40%的数据,1≤n≤102;
对于60%的数据,1≤n≤103;
对于100%的数据,1≤T≤10,1≤n≤105,∑n≤2×105,0≤m≤n−1,输入数据保证不会形成环,且每棵树的大小≤5×104。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4
2 1
1 2
3 2
1 2
1 3
2 0
3 1
1 2
Alice
Alice
Bob
Alice
样例 2
5
10 5
4 3
4 5
10 4
9 10
7 2
15 10
11 4
6 7
8 3
12 1
14 10
6 9
11 1
14 11
5 9
14 13
20 16
2 10
12 14
9 8
4 6
9 12
12 5
5 11
18 14
4 10
12 15
5 13
6 17
19 3
1 8
19 7
8 6
20 17
8 5
17 1
6 5
11 10
20 16
1 3
9 5
20 19
9 18
13 7
7 12
11 20
6 11
15 9
17 14
4 14
16 2
20 19
16 10
9 4
20 4
8 4
10 18
7 9
5 19
19 2
7 12
1 16
9 11
4 14
3 12
16 7
13 7
6 4
17 9
5 4
5 15
Alice
Bob
Bob
Alice
Alice