Given a tree with $n$ vertices, labeled from $1$ to $n$. The $i$-th edge ($1 \le i \le n-1$) connects vertices $u_i$ and $v_i$.

We want to assign a direction to each edge of the tree. Any orientation can be described by a string $S = s_1s_2 \cdots s_{n - 1}$ of length $n - 1$, where $s_i = 0$ means the $i$-th edge is directed as $u_i \rightarrow v_i$, and $s_i = 1$ means it is directed as $v_i \rightarrow 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\cdots s_{n-1}$ is lexicographically smaller than $T=t_1t_2\cdots t_{n-1}$ if there exists an index $k$ such that $s_1=t_1, s_2=t_2, \cdots, s_{k-1}=t_{k-1}$ and $s_k < t_k$.

Input

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

The next $n - 1$ lines each contain two positive integers $u_i, v_i$, representing an edge of the tree. It is guaranteed that 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 \le a_i, b_i \le n$ and $a_i \ne b_i$.

Output

Output a single line containing a string $S = s_1 \cdots s_{n - 1}$, representing the $01$ string corresponding to the lexicographically smallest perfect orientation.

Examples

Input 1

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

Output 1

001

Note 1

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

Input 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 2

10101

Note 2

In this sample, a set of perfect orientations must satisfy that $4$ cannot reach $3$ and $5$ cannot reach $1$, so $s_1 = s_5 = 1$. If $s_2 = s_3 = 0$, then there exists a path $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$, so $1$ can reach $4$, which means it is not a perfect orientation. Therefore, all perfect orientations must satisfy that $S$ is lexicographically no smaller than $10101$. It is easy to verify that when $S = 10101$, the corresponding orientation is a perfect orientation.

Constraints

For all test data, it is guaranteed that: $2 \leq n \leq 5 \times 10 ^ 5$, $1 \leq m \leq 5 \times 10 ^ 5$, and at least one perfect orientation exists.

Special Property A: It is guaranteed that $(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: It is guaranteed that the vertex labeled $1$ in the tree is adjacent to every other vertex.