QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 2048 MB Total points: 100
[+19]
Statistics

题目描述

给定一棵含有 n 个顶点的树,顶点从 1n 编号。树上第 i1in1)条边连接顶点 uivi

现在,我们想要给树的每条边一个定向。任何一个定向都可以用一个长度为 n1 的字符串 S=s1s2sn1 来描述。其中,si=0 代表第 i 条边定向为 uivi,否则 si=1 代表第 i 条边定向为 viui​​。

给定 m 个顶点对 (ai,bi),其中 1ai,binaibi

一个完美定向定义为:在此定向下,对于任意 1imai 不能到达 bi

试求在所有完美定向中,所对应的字符串字典序最小的定向。数据保证存在至少一个完美定向。

定义字符串 S=s1s2sn1 的字典序小于 T=t1t2tn1 若存在一个下标 k 使得 s1=t1,s2=t2,,sk1=tk1sk<tk

输入格式

从标准输入读入数据。

输入的第一行包含三个非负整数 c,n,m,分别表示测试点编号,树的点数,顶点对的个数。c=0 表示该测试点为样例。

接下来 n1 行,每行包含两个正整数 ui,vi 表示树的一条边。保证这 n1 条边构成了一棵树。

接下来 m 行,每行包含两个正整数 ai,bi。保证 1ai,binaibi

输出格式

输出到标准输出。

输出一行包含一个字符串 S=s1sn1,表示字典序最小的完美定向所对应的 01 字符串。

样例

输入

0 4 2
1 2
2 3
3 4
3 2
1 4

输出

001

解释

在该样例中,若 S=000,则该定向中 1 能到达 4 (存在路径 1234),因而不是完美定向。若 S=001,则该定向中 3 不能到达 21 不能到达 4,因而是完美定向。故答案为 001

样例

输入

0 6 8
5 1
2 3
1 2
5 6
4 3
4 3
5 1
6 3
5 4
1 4
5 2
3 6
6 2

输出

10101

解释

在该样例中,一组完美定向必定满足 4 不能到达 35 不能到达 1,故 s1=s5=1。若 s2=s3=0,则存在路径 1234,故 1 可到达 4,故它不是完美定向。因此,所有完美定向必定满足 S 的字典序不小于 10101。且容易验证 S=10101 时,对应的定向是完美定向。

样例三

ex_3.inex_3.ans

这个样例满足测试点 13 的约束条件。

样例四

ex_4.inex_4.ans

这个样例满足测试点 46 的约束条件。

样例五

ex_5.inex_5.ans

这个样例满足测试点 7,8 的约束条件。

样例六

ex_6.inex_6.ans

这个样例满足测试点 9,10 的约束条件。

数据范围

对于所有测试数据保证:2n5×1051m5×105且存在至少一个完美定向

测试点编号 n m 特殊性质
13 15 50
46 300 300
7,8 400 =(n1)(n2) A
9,10 2000 2000 B
1114
15,16 105 105 B
17,18
1921 2×105 2×105
2225 5×105 5×105

特殊性质 A: 保证 (a,b) 出现在 (ai,bi) 中当且仅当 aba,b 在树上不相邻。

特殊性质 B: 保证树上编号为 1 的顶点与其他每个顶点均相邻。