给定一棵含有 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$ 字符串。

【样例 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}

• 特殊性质 A：保证 (a,b) 出现在 (a_i,b_i) 中当且仅当 a\neq b 且 a,b 在树上不相邻。
• 特殊性质 B：保证树上编号为 1 的顶点与其他每个顶点均相邻。

NOI