UOJ Logo Universal Online Judge

UOJ

#266. 【清华集训2016】Alice和Bob又在玩游戏

统计

Alice 和 Bob 又在玩游戏。

有 $n$ 个节点,$m$ 条边($0 \le m \le 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 \le n \le 20$;

对于$40 \%$的数据,$1 \le n \le 10^2$;

对于$60 \%$的数据,$1 \le n \le 10^3$;

对于$100 \%$的数据,$1 \le T \le 10, 1 \le n \le 10^5, \sum{n} \le 2 \times 10^5, 0 \le m \le n-1$,输入数据保证不会形成环,且每棵树的大小$\le 5 \times 10^4$。

时间限制:$2\texttt{s}$

空间限制:$1024\texttt{MB}$

下载

样例数据下载