Problem Description

Given a tree with $n$ vertices numbered from $1$ to $n$, where the $i$-th edge (for $1 \leq i \leq n-1$) connects vertices $u_i$ and $v_i$.

We want to orient each edge in the tree. Any orientation can be described by a string $S = s_1s_2 \ldots s_{n-1}$ of length $n-1$, where $s_i = 0$ means the $i$-th edge is oriented from $u_i$ to $v_i$, and $s_i = 1$ means the $i$-th edge is oriented from $v_i$ to $u_i$.

Given $m$ pairs of vertices $(a_i, b_i)$, where $1 \leq a_i, b_i \leq n$ and $a_i \neq b_i$.

A perfect orientation is defined as an orientation where, for any $1 \leq i \leq m$, $a_i$ cannot reach $b_i$.

Find the lexicographically smallest string $S$ among all perfect orientations. It is guaranteed that at least one perfect orientation exists.

A string $S = s_1s_2 \ldots s_{n-1}$ is lexicographically smaller than $T = t_1t_2 \ldots t_{n-1}$ if there exists an index $k$ such that $s_1 = t_1, s_2 = t_2, \ldots, s_{k-1} = t_{k-1}$ and $s_k < t_k$.

Input Format

The first line contains three non-negative integers $c, n, m$, representing the test case number, the number of vertices in the tree, and the number of vertex pairs, respectively. Here, $c = 0$ indicates a sample test case.

The next $n-1$ lines each contain two positive integers $u_i, v_i$ representing an edge in the tree. It is guaranteed that $1 \leq u_i, v_i \leq n$ and these $n-1$ edges form a tree.

The next $m$ lines each contain two positive integers $a_i, b_i$. It is guaranteed that $1 \leq a_i, b_i \leq n$ and $a_i \neq b_i$.

Output Format

Output a single line containing a string $S = s_1s_2 \ldots s_{n-1}$, which represents the lexicographically smallest perfect orientation as a binary string.

Sample Input and Output

Input Sample #1

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

Output Sample #1

001

Input Sample #2

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

Output Sample #2

10101

Input Sample #3

See tree3.in/tree3.ans
This sample satisfies the constraints for test points 1-3.

Output Sample #3

Input Sample #4

See tree4.in/tree4.ans
This sample satisfies the constraints for test points 4-6.

Output Sample #4

Input Sample #5

See tree5.in/tree5.ans
This sample satisfies the constraints for test points 7,8.

Output Sample #5

Input Sample #6

See tree6.in/tree6.ans
This sample satisfies the constraints for test points 9,10.

Output Sample #6

Notes/Hints

[Sample 1 Explanation]

In this sample, if $S = 000$, then vertex $1$ can reach vertex $4$ (path $1 \to 2 \to 3 \to 4$), so it is not a perfect orientation. If $S = 001$, then vertex $3$ cannot reach vertex $2$ and vertex $1$ cannot reach vertex $4$, so it is a perfect orientation. Hence, the answer is $001$.

[Sample 2 Explanation]

In this sample, a perfect orientation must ensure that vertex $4$ cannot reach vertex $3$ and vertex $5$ cannot reach vertex $1$. Thus, $s_1 = s_5 = 1$. If $s_2 = s_3 = 0$, there exists a path $1 \to 2 \to 3 \to 4$, so vertex $1$ can reach vertex $4$. Therefore, it is not a perfect orientation. Hence, all perfect orientations must have $S$ lexicographically not smaller than $10101$. It is easy to verify that when $S = 10101$, the corresponding orientation is perfect.

[Data Range]

For all test data, it is guaranteed that $2 \leq n \leq 5 \times 10^5$, $1 \leq m \leq 5 \times 10^5$, $1 \leq u_i, v_i \leq n$, and all edges form a tree. Also, $1 \leq a_i, b_i \leq n$ and $a_i \neq b_i$.

It is guaranteed that at least one perfect orientation exists.

• Special Property A: $(a, b)$ appears in $(a_i, b_i)$ if and only if $a \neq b$ and $a, b$ are not adjacent in the tree.
• Special Property B: The vertex numbered $1$ is adjacent to every other vertex in the tree.

见题面 Input 部分

见题面 Output 部分