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

单点时限: 6.0 sec

内存限制: 1024 MB

星光镇的城域网建设已经拥有上百年的历史。在该城域网建设的初期,生成树协议还尚未被发明。所以整个网络在硬件上就被建设成了一棵树的拓补结构:也就是说,任意两台交换机之间帧交换有且仅有唯一的一条路径。该网络流畅地运行至今,直到最近星光镇政府面临财政紧缺------他们已经没有更多的钱维护这一网络了。他们决定对网络配置进行降级。

下面所要提及的降级方案可能听起来很不可思议,但是星光镇老板唐纳德先生似乎总能自圆其说。在他看来,双向链路就是一种浪费,一般来说发出去的报文不需要回复;同样的,带有出口选择功能的交换机也是一种浪费,交换机不应该插手路径的选择,它只要把收到的东西往一个方向发就好了。

这样做一定会带来某些需求得不到满足。不过唐纳德先生把已经备案的需求,按照缴纳的需求费用排了个序。于是作为网管部门,你只需要满足 条需求,其中第 条需求就表明 需要向 发送帧。

现在我们将整个故事再形式化一下。有一个 个点的无根树,现在要求给每条边定向,使得每个点的出度至多为 ,并且对所有 满足 有通路。

输入格式

第一行一个整数 (),表示数据组数。

对于每组数据,首先有一行三个整数 (, )。

接下来 行,第 行两个整数 (, ) 表示 之间有一条无向边。保证无序对 在同组数据中至多出现一次。

接下来 行,第 行两个整数 (, )。有序对 可能出现多次。

输入保证所有测试数据的 不超过

输出格式

对于每组数据,输出一个长度为 的字符串。第 个字符表示第 条边的方向,D 表示从 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 人解决,34 人已尝试。

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

7.2 EMB 奖励。

创建: 9 月前.

修改: 9 月前.

最后提交: 3 周前.

来源: EOJ Monthly 2019.1

题目标签