给定一棵含有 $n$ 个顶点的树，顶点从 $1$ 到 $n$ 编号，树上第 $i(1\leq i\leq n-1)$ 条边连接顶点 $u_i$ 和 $v_i$。
现在，我们想要给树的每条边一个定向。任何一个定向都可以用一个长度为 $n-1$ 的字符串 $S=s_1s_2\ldots 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_1s_2\ldots s_{n-1}$ 的字典序小于 $T=t_1t_2\ldots t_{n-1}$ 若存在一个下标 $k$ 使得 $s_1=t_1, s_2=t_2, \ldots, s_{k-1}=t_{k-1}$ 且 $s_k < t_k$。
## Input
输入的第一行包含三个非负整数 $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$。
## Output
输出一行包含一个字符串 $S=s_1s_2\ldots s_{n-1}$，表示字典序最小的完美定向所对应的 $01$ 字符串。
[samples]
## Background
由于评测机性能差异，原题时限为 3s，洛谷上时限为 6s。
## Note
**【样例 1 解释】**
在该样例中，若 $S=000$，则该定向中 $1$ 能到达 $4$（存在路径 $1\to 2\to 3\to 4$），因而不是完美定向。若 $S=001$，则该定向中 $3$ 不能到达 $2$，$1$ 不能到达 $4$，因面是完美定向。故答案为 $001$。
**【样例 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$ 时，对应的定向是完美定向。
**【数据范围】**
对于所有测试数据保证 $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$。
数据保证存在至少一个完美定向。
::cute-table{tuack}
| 测试点编号 | $n$ | $m$ | 特殊性质 |
| :----------: | :----------: | :----------: | :----------: |
| $1\sim 3$ | $\leq 15$ | $\leq 50$ | 无 |
| $4\sim 6$ | $\leq 300$ | $\leq 300$ | 无 |
| $7,8$ | $\leq 400$ | $=(n-1)(n-2)$ | A |
| $9,10$ | $\leq 2\,000$ | $\leq 2\,000$ | B |
| $11\sim 14$ | $\leq 2\,000$ | $\leq 2\,000$ | 无 |
| $15,16$ | $\leq 10^5$ | $\leq 10^5$ | B |
| $17,18$ | $\leq 10^5$ | $\leq 10^5$ | 无 |
| $19\sim 21$ | $\leq 2\times 10^5$ | $\leq 2\times 10^5$ | 无 |
| $22\sim 25$ | $\leq 5\times 10^5$ | $\leq 5\times 10^5$ | 无 |
- 特殊性质 A：保证 $(a,b)$ 出现在 $(a_i,b_i)$ 中当且仅当 $a\neq b$ 且 $a,b$ 在树上不相邻。
- 特殊性质 B：保证树上编号为 $1$ 的顶点与其他每个顶点均相邻。