Background

Due to performance differences among judging machines, the original time limit was $3\ \mathrm{s}$, while on Luogu the time limit is $6\ \mathrm{s}$.

Problem Description

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

Now we want to assign a direction to every edge of the tree. Any orientation can be described by a string $S=s_1s_2\ldots s_{n-1}$ of length $n-1$. Here, $s_i=0$ means the $i$-th edge is directed as $u_i \to v_i$; otherwise, $s_i=1$ means the $i$-th edge is directed as $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 follows: under this orientation, for every $1\leq i\leq m$, $a_i$ cannot reach $b_i$.

Among all perfect orientations, find the one whose corresponding string is lexicographically smallest. It is guaranteed that at least one perfect orientation exists.

We say the lexicographical order of $S=s_1s_2\ldots s_{n-1}$ is 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 point ID, the number of vertices in the tree, and the number of vertex pairs. Here $c=0$ means this test point is a sample.

The next $n-1$ lines each contain two positive integers $u_i,v_i$, describing an edge of 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 one line containing a string $S=s_1s_2\ldots s_{n-1}$, the $01$ string corresponding to the lexicographically smallest perfect orientation.

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

见 tree3.in/tree3.ans
这个样例满足测试点 1-3 的约束条件。

见 tree4.in/tree4.ans
这个样例满足测试点 4-6 的约束条件。

见 tree5.in/tree5.ans
这个样例满足测试点 7,8 的约束条件。

见 tree6.in/tree6.ans
这个样例满足测试点 9,10 的约束条件。

Hint

[Sample 1 Explanation]

In this sample, if $S=000$, then in this orientation $1$ can reach $4$ (there is a path $1\to 2\to 3\to 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. Therefore the answer is $001$.

[Sample 2 Explanation]

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

[Constraints]

For all testdata, 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; $1\leq a_i,b_i \leq n$ and $a_i\neq b_i$.

It is guaranteed that at least one perfect orientation exists.

::cute-table{tuack}

• 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 numbered $1$ is adjacent to every other vertex in the tree.

Translated by ChatGPT 5