[清华集训2016] Alice 和 Bob 又在玩游戏

题目描述

Alice 和 Bob 在玩游戏。 有 $n$ 个节点,$m$ 条边 $(0\le m\le n-1)$ ,构成若干棵有根树,每棵树的根节点是该连通块内编号最小的点。Alice 和 Bob 轮流操作,每回合选择一个没有被删除的节点 $x$,将 $x$ 及其所有祖先全部删除,不能操作的人输。 注:树的形态是在一开始就确定好的,删除节点不会影响剩余节点父亲和儿子的关系。比如:$1-3-2$ 这样一条链 ,$1$ 号点是根节点,删除 $1$ 号点之后,$3$ 号点还是 $2$ 号点的父节点。 问有没有先手必胜策略。

输入输出格式

输入格式


**本题有多组数据。** 第一行一个正整数 $T$,表示该测试点有 $T$ 组数据;接下来 $T$ 组数据。 对于每组数据: 输入第一行两个整数 $n, m$,分别表示点数和边数(节点从 $1$ 开始编号)。 接下来 $m$ 行,每行两个正整数 $a, b$,表示节点 $a$ 和节点 $b$ 之间有一条边,输入数据中没有重边。

输出格式


输出 $T$ 行,每行输出 Alice 先手并且 Alice 和 Bob 都足够聪明的情况下谁获胜。

输入输出样例

输入样例 #1

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

输出样例 #1

Alice
Alice
Bob
Alice

说明

#### 样例解释 第一组数据输入是一条链,Alice 可以一次性把所有节点都删掉。 第二组数据,Alice 先手第一步删除 $1$ 号点即可胜利。 #### 数据范围 对于 $100\%$ 的数据,$1≤T≤10$,$1≤n≤10^5$,$∑n≤2×10^5$,$0≤m≤n−1$,输入数据保证不会形成环,且每棵树的大小 $≤5×10^4$。