题目描述

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

现在，我们想要给树的每条边一个定向。任何一个定向都可以用一个长度为 $n - 1$ 的字符串 $S = s_1s_2 \cdots s_{n - 1}$ 来描述。其中，$s_i = 0$ 代表第 $i$ 条边定向为 $u_i \rightarrow v_i$，否则 $s_i = 1$ 代表第 $i$ 条边定向为 $v_i \rightarrow 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_1s_2\cdots s_{n-1}$ 的字典序小于 $T=t_1t_2\cdots t_{n-1}$ 若存在一个下标 $k$ 使得 $s_1=t_1, s_2=t_2, \cdots, s_{k-1}=t_{k-1}$ 且 $s_k < t_k$。

输入格式

从标准输入读入数据。

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

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

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

输出格式

输出到标准输出。

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

样例

输入

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

输出

001

解释

在该样例中，若 $S = 000$，则该定向中 $1$ 能到达 $4$ (存在路径 $1 \rightarrow 2 \rightarrow 3 \rightarrow 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

解释

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

样例三

见下载目录下的 ex_3.in 与 ex_3.ans。

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

样例四

见 ex_4.in 与 ex_4.ans。

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

样例五

见 ex_5.in 与 ex_5.ans。

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

样例六

见 ex_6.in 与 ex_6.ans。

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

数据范围

对于所有测试数据保证：$2 \leq n \leq 5 \times 10 ^ 5$，$1 \leq m \leq 5 \times 10 ^ 5$，且存在至少一个完美定向。

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

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