[NOI2024] 树的定向

给定一棵含有 $n$ 个顶点的树，顶点编号为 $1\sim n$。第 $i$ 条边连接 $u_i$ 和 $v_i$。

你需要给每条边定向。用长度为 $n-1$ 的字符串 $S=s_1s_2\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\le i\le m$，顶点 $a_i$ 都不能到达顶点 $b_i$，则称它为完美定向。

数据保证至少存在一个完美定向。请输出所有完美定向中字典序最小的字符串。

输入格式

第一行包含三个非负整数 $c,n,m$。$c$ 是测试点编号，$c=0$ 表示样例。

接下来 $n-1$ 行，第 $i$ 行包含两个整数 $u_i,v_i$，描述树的第 $i$ 条边。

接下来 $m$ 行，每行包含两个整数 $a_i,b_i$，描述一项不可达限制。

输出格式

输出一行一个长度为 $n-1$ 的 01 字符串，表示字典序最小的完美定向。

样例输入

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

样例输出

001

数据范围

对于所有测试数据：

• $2\le n\le 5\times 10^5$；
• $0\le m\le 5\times 10^5$；
• $1\le u_i,v_i,a_i,b_i\le n$，$a_i\ne b_i$；
• 给出的 $n-1$ 条边构成一棵树；
• 至少存在一个完美定向。

来源与许可

本题为 CCF NOI 2024 第一试第三题「树的定向（tree）」。题面与测试数据来自 NOI 官网发布页，按 CC BY-NC 4.0 使用。原赛制使用 tree.in / tree.out 文件输入输出；本平台等价适配为标准输入输出。