3672. 唐纳德先生与网络降级计划

单点时限: 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 反之。

输入保证有解。若有多解,输出任意一解。

样例

Input
2
2 1
2 1
1 2
5 1
1 2
2 3
3 4
3 5
1 5
Output
C
DDCD
Input
1
4 4
1 2
1 3
1 4
3 4
2 4
2 1
1 4
Output
CCD

13 人解决,35 人已尝试。

15 份提交通过,共有 174 份提交。

7.2 EMB 奖励。

创建: 1 年,9 月前.

修改: 1 年,9 月前.

最后提交: 10 月,3 周前.

来源: EOJ Monthly 2019.1

题目标签