EOJ Monthly 2019.1

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

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

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

现在我们将整个故事再形式化一下。有一个 $n$ 个点的无根树，现在要求给每条边定向，使得每个点的出度至多为 $1$，并且对所有 $1\le i\le q$ 满足 $s_i$ 到 $t_i$ 有通路。