题目描述

给定一棵含有 $n$ 个顶点的树，顶点从 $1$ 到 $n$ 编号，树上第 $i$（$1 \leq i \leq n - 1$）条边连接顶点 $u_i$ 和 $v_i$。

现在，我们想要给树的每条边一个定向。任何一个定向都可以用一个长度为 $n - 1$ 的字符串 $S = s_1 s_2 \cdots s_{n-1}$ 来描述。其中 $s_i = 0$ 代表第 $i$ 条边定向为 $u_i \to v_i$，否则 $s_i = 1$ 代表第 $i$ 条边定向为 $v_i \to u_i$。

给定 $m$ 个顶点对 $(a_i, b_i)$，其中 $1 \leq a_i, b_i \leq n$ 且 $a_i \neq b_i$。

一个 完美定向 定义为：在此定向下，对于任意 $1\leq i\leq m$，$a_i$ 不能到达 $b_i$。

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

定义字符串 $S = s_1 \cdots s_{n-1}$ 的字典序小于 $T = t_1 \cdots t_{n-1}$：若存在一个下标 $k$ 使得 $s_1 = t_1, s_2 = t_2, \cdots, s_{k-1} = t_{k-1}$ 且 $s_k < t_k$。

输入格式

从文件 tree.in 中读入数据。

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

接下来 $n - 1$ 行，每行包含两个正整数 $u_i, v_i$ 表示树的一条边。保证 $1 \leq u_i, v_i \leq n$ 且这 $n - 1$ 条边构成了一棵树。

接下来 $m$ 行，每行包含两个正整数 $a_i, b_i$。保证 $1 \leq a_i, b_i \leq n$ 且 $a_i \neq b_i$。

输出格式

输出到文件 tree.out 中。

输出一行包含一个字符串 $S = s_1 \cdots s_{n-1}$，表示字典序最小的完美定向所对应的 $01$ 字符串。

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

001

样例 1 解释

在该样例中，若 $S = 000$，则该定向中 $1$ 能到达 $4$（存在路径 $1 \to 2 \to 3 \to 4$），因而不是完美定向。若 $S = 001$，则该定向中 $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

样例 2 解释

在该样例中，一组完美定向必定满足 $4$ 不能到达 $3$，$5$ 不能到达 $1$，故 $s_1 = s_5 = 1$。若 $s_2 = s_3 = 0$，则存在路径 $1 \to 2 \to 3 \to 4$，故 $1$ 可到达 $4$，故其不是完美定向。因此，所有完美定向必定满足 $S$ 的字典序不小于 $10101$。且容易验证 $S = 10101$ 时，对应的定向是完美定向。

样例 3

见选手目录下的 tree/tree3.in 与 tree/tree3.ans。

这个样例满足测试点 $1 \sim 3$ 的约束条件。

样例 4

见选手目录下的 tree/tree4.in 与 tree/tree4.ans。

这个样例满足测试点 $4 \sim 6$ 的约束条件。

样例 5

见选手目录下的 tree/tree5.in 与 tree/tree5.ans。

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

样例 6

见选手目录下的 tree/tree6.in 与 tree/tree6.ans。

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

数据范围

对于所有测试数据保证：$2 \leq n \leq 5 \times 10^5$，$1 \leq m \leq 5 \times 10^5$，$1 \leq u_i, v_i \leq n$ 且所有的边构成了一棵树，$1 \leq a_i, b_i \leq n$ 且 $a_i \neq b_i$。

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

测试点编号	$n$	$m$	特殊性质
$1 \sim 3$	$\leq 15$	$\leq 50$	无
$4 \sim 6$	$\leq 300$
$7, 8$	$\leq 400$	$= (n-1)(n-2)$	A
$9, 10$	$\leq 2\,000$		B
$11 \sim 14$			无
$15, 16$	$\leq 10^5$		B
$17, 18$			无
$19 \sim 21$	$\leq 2 \times 10^5$
$22 \sim 25$	$\leq 5 \times 10^5$

特殊性质 A：保证 $(a, b)$ 出现在 $(a_i, b_i)$ 中当且仅当 $a \neq b$ 且 $a, b$ 在树上不相邻。

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