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`（表示平局）。

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

ABDD
DBD