13 人解决，37 人已尝试。
15 份提交通过，共有 187 份提交。
7.3 EMB 奖励。
单点时限: 6.0 sec
内存限制: 1024 MB
星光镇的城域网建设已经拥有上百年的历史。在该城域网建设的初期，生成树协议还尚未被发明。所以整个网络在硬件上就被建设成了一棵树的拓补结构：也就是说，任意两台交换机之间帧交换有且仅有唯一的一条路径。该网络流畅地运行至今，直到最近星光镇政府面临财政紧缺------他们已经没有更多的钱维护这一网络了。他们决定对网络配置进行降级。
下面所要提及的降级方案可能听起来很不可思议，但是星光镇老板唐纳德先生似乎总能自圆其说。在他看来，双向链路就是一种浪费，一般来说发出去的报文不需要回复；同样的，带有出口选择功能的交换机也是一种浪费，交换机不应该插手路径的选择，它只要把收到的东西往一个方向发就好了。
这样做一定会带来某些需求得不到满足。不过唐纳德先生把已经备案的需求，按照缴纳的需求费用排了个序。于是作为网管部门，你只需要满足 $q$ 条需求，其中第 $i$ 条需求就表明 $s_i$ 需要向 $t_i$ 发送帧。
现在我们将整个故事再形式化一下。有一个 $n$ 个点的无根树，现在要求给每条边定向，使得每个点的出度至多为 $1$，并且对所有 $1 \le i \le q$ 满足 $s_i$ 到 $t_i$ 有通路。
第一行一个整数 $t$ ($1 \le t \le 10^5$)，表示数据组数。
对于每组数据，首先有一行三个整数 $n, q$ ($2 \le n \le 10^6$, $1 \le q \le 10^6$)。
接下来 $n-1$ 行，第 $i$ 行两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$) 表示 $u_i$ 和 $v_i$ 之间有一条无向边。保证无序对 $(u_i, v_i)$ 在同组数据中至多出现一次。
接下来 $q$ 行，第 $i$ 行两个整数 $s_i, t_i$ ($1 \le s_i, t_i \le n$, $s_i \ne t_i$)。有序对 $(s_i, t_i)$ 可能出现多次。
输入保证所有测试数据的 $\Sigma n, \Sigma q$ 不超过 $10^6$。
对于每组数据，输出一个长度为 $n-1$ 的字符串。第 $i$ 个字符表示第 $i$ 条边的方向，D 表示从 $u_i$ 到 $v_i$，C 反之。
输入保证有解。若有多解，输出任意一解。
2 2 1 2 1 1 2 5 1 1 2 2 3 3 4 3 5 1 5
C DDCD
1 4 4 1 2 1 3 1 4 3 4 2 4 2 1 1 4
CCD
13 人解决，37 人已尝试。
15 份提交通过，共有 187 份提交。
7.3 EMB 奖励。