题目描述

Alice 和 Bob 又在玩游戏。

有 \(n\) 个节点，\(m\) 条边（\(0 \leq m \leq 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 都足够聪明的情况下谁获胜。

样例 1

输入

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

输出

Alice
Alice
Bob
Alice

解释

输入共 4 组数据；

第一组数据输入是一条链，Alice 可以一次性把所有节点都删掉。

第二组数据，Alice 先手第一步删除 \(1\) 号点即可胜利。

样例二

见下发文件。

样例三

见下发文件。

数据范围限制

对于\(10\%\)的数据，\(m = 0\)；
对于\(20\%\)的数据，\(1 \leq n \leq 20\)；
对于\(40\%\)的数据，\(1 \leq n \leq 10^2\)；
对于\(60\%\)的数据，\(1 \leq n \leq 10^3\)；
对于\(100\%\)的数据，\(1 \leq T \leq 10\)，\(1 \leq n \leq 10^5\)，\(\sum n \leq 2 \times 10^5\)，\(0 \leq m \leq n-1\)，输入数据保证不会形成环，且每棵树的大小 \(\leq 5 \times 10^4\)。

限制

每个测试点时限：2秒
内存限制：1024MB

来源

清华集训2016