给定一棵含有 n 个顶点的树，顶点从 1 到 n 编号，树上第 i(1\leq i\leq n-1) 条边连接顶点 u_i 和 v_i。
现在，我们想要给树的每条边一个定向。任何一个定向都可以用一个长度为 n-1 的字符串 $S=s_1s2\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_1s2\ldots s{n-1} 的字典序小于 T=t_1t2\ldots t{n-1} 若存在一个下标 k 使得 s_1=t_1, s_2=t2, \ldots, s{k-1}=t_{k-1} 且 s_k < t_k$。
输入的第一行包含三个非负整数 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。
输出一行包含一个字符串 $S=s_1s2\ldots s{n-1}，表示字典序最小的完美定向所对应的 01$ 字符串。
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 解释】
在该样例中，若 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 | 无 |
NOI