Alice 和 Bob 在一张简单无向图上博弈，Alice 先手。每次每人必须沿着当前所在的点的一条边走到另一端，不能走到对手所在的位置，不能行动者输。

对于每个 $i$ 从$1$ 到 $n−1$，求出 Alice 初始在 $1$ 号点，Bob 初始在 $i+1$ 号点，谁会赢或平局。

本题有多组数据。第一行一个正整数 $T（1≤T≤10101）$，表示测试数据组数。

对于每组数据，第一行两个非负整数 $n,m（2≤n≤2⋅10^5 ,0≤m≤2⋅10^5）$。

接下来 $m$ 行每行两个正整数 $u,v$ 表示一条无向边。保证图是简单无向图，即无重边自环。

保证 $∑n≤10^6 ,∑m≤1020304$。

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