题目描述

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 都足够聪明的情况下谁获胜。

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

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