SunBoYi

Problem Description

Alice 和 Bob 在一张简单无向图上博弈，Alice 先手。每次每人必须沿着当前所在的点的一条边走到另一端，不能走到对手所在的位置，不能行动者输。 对于每个 $i$ 从 $1$ 到 $n-1$，求出 Alice 初始在 $1$ 号点，Bob 初始在 $i+1$ 号点，谁会赢或平局。

Input

本题有多组数据。第一行一个正整数 $T$（$1\le T\le 10101$），表示测试数据组数。 对于每组数据，第一行两个非负整数 $n,m$（$2\le n\le2\cdot10^5,0\le m\le2\cdot10^5$）。 接下来 $m$ 行每行两个正整数 $u,v$ 表示一条无向边。保证图是简单无向图，即无重边自环。 保证 $\sum n\le10^6,\sum m\le1020304$。

Output

对于每组数据输出一个长为 $n-1$ 的字符串，其中第 $i$ 个字符为 A 或 B 或 D 表示该 $i$ 对应的答案为 Alice 或 Bob 或 Draw（表示平局）。

Sample Input

2
5 5
1 3
2 3
3 4
3 5
4 5
4 2
1 3
2 4

Sample Output

ABDD
DBD

Source

2024“钉耙编程”中国大学生算法设计超级联赛（10）