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}$

下载

样例数据下载