#10000218. 【NOI 2024 Day 1】树的定向（tree）

提交源程序文件名

【题目描述】

给定一棵含有 个顶点的树，顶点从 到 编号。树上第 （）条边连接顶点 和 。

现在，我们想要给树的每条边一个定向。任何一个定向都可以用一个长度为 的字符串 来描述。其中， 代表第 条边定向为 ，否则 代表第 条边定向为 。

给定 个顶点对 ，其中 且

一个完美定向定义为：在此定向下，对于任意 ， 不能到达 。

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

定义字符串 的字典序小于 ：若存在一个下标 ，使得 。

【输入格式】

从文件 中读入数据。

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

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

接下来 行，每行包含两个正整数 。保证 且

【输出格式】

输出到文件 中。

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

【样例 输入】

0 4 2
1 2
2 3
3 4
3 2
1 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

【样例 解释】

在该样例中，一组完美定向必定满足 不能到达 ， 不能到达 ，故 。若 ，则存在路径 ，故 可到达 ，故其不是完美定向。因此，所有完美定向必定满足 的字典序不小于 。且容易验证 时，对应的定向是完美定向。

【样例 】

见选手目录下的 与 。

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

【样例 】

见选手目录下的 与 。

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

【样例 】

见选手目录下的 与 。

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

【样例 】

见选手目录下的 与 。

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

【数据范围】

对于所有测试数据保证：，， 且所有的边构成了一棵树， 且 。

数据保证存在至少一个完美定向。

特殊性质 : 保证 出现在 中当且仅当 且 在树上不相邻。

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