[AdditionalFile5403.zip](file://AdditionalFile5403.zip?type=additional_file)

#5403. 「OOI 2020 Day 1」制定票价

标签: 传统 | 时间限制: 6000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2020 Day1 T3 「Интересные конкурсы / Assigning Fares」。

M 市的市长决定在 2020 年开通几条新的地铁线路。由于城市预算非常有限，他决定不挖掘新的隧道，而是利用现有的地下网络。

M 市的隧道系统包含 $n$ 个地铁站。这些车站通过 $n-1$ 个双向隧道连接，任意两个车站 $v$ 和 $u$ 之间恰好存在一条简单路径。市长希望创建的每条地铁线路是从车站 $a_i$ 到车站 $b_i$ 的简单路径。这些线路可能相交，即可能有公共的车站或隧道。然而，每条线路的列车运行方向尚未确定。也就是说，在车站 $a_i$ 和 $b_i$ 之间的路径上，列车可以从 $a_i$ 到 $b_i$ 运行，也可以从 $b_i$ 到 $a_i$ 运行，但只能选择一个方向。

M 市采用一种特殊的票价系统。每座车站被分配一个正整数 $c_i$，表示该车站的票价区。从车站 $v$ 到车站 $u$ 的票价定为 $c_u - c_v$ 伯利。当然，只有当存在一条从 $v$ 到 $u$ 运行的列车线路时，这种移动才是允许的。市长不希望在任何一条线路上的两个车站之间出现负票价，因此决定选择列车运行方向并调整所有车站的票价区，使得每条线路上的票价区在列车运行方向上严格递增。

市长首先希望为每个车站分配票价区，然后选择所有地铁线路的方向，使得沿每条线路的票价区严格递增。由于城市日即将到来，在所有可能的票价区分配方案中，市长希望选择一个使最大 $c_i$ 尽可能小的方案。帮助市长制定新的分配方案，或者告知他这是不可能的。请注意，你只需要以最优方式分配票价区，无需输出线路的方向。只要存在一种选择线路方向的方式，使得所有线路上的票价区沿运行方向严格递增，你的解决方案即被认为是正确的。

此外，在某些子任务中，无需最小化答案，仅需确定是否可能以所需方式分配票价区。

输入格式

第一行包含三个整数 $n, m, t$ $(2 \leq n \leq 500000, 1 \leq m \leq 500000, 0 \leq t \leq 1)$，分别表示城市中的车站数量、地铁线路数量以及测试参数 $t$。如果 $t = 0$，则不需要最小化答案；如果 $t = 1$，则要求最小化最高票价区的编号。

接下来的 $n-1$ 行描述地铁隧道。每条隧道由两个整数 $v_i, u_i$ $(1 \leq v_i, u_i \leq n, v_i \neq u_i)$表示。保证任意两个车站之间恰好存在一条简单路径。

接下来的 $m$ 行描述地铁线路。每条线路由两个整数 $a_i, b_i$ $(1 \leq a_i, b_i \leq n,a_i \neq b_i)$ 表示。

输出格式

第一行输出一个整数 $k$，即最大票价区编号。如果测试参数 $t = 0$，则无需最小化 $k$；如果 $t = 1$，则 $k$ 必须是可能的最小值。

第二行输出 $n$ 个数字 $c_1, c_2, \ldots, c_n$ $(1 \leq c_i \leq k)$，表示各车站的票价区。

如果存在多个答案，输出其中任意一个。如果无法以所需方式分配票价区，则输出 -1。

样例 1

输入

3 1 1
1 2
2 3
1 3

输出

3
1 2 3

在第一个样例中，线路 $1 \rightarrow 3$ 经过车站顺序为 $1, 2, 3$。在此顺序下，车站的票价区是递增的。由于这条线路有 $3$ 个车站，因此至少需要 $3$ 个票价区。因此，答案 $1, 2, 3$ 是最优的。

样例 2

输入

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

输出

-1

在第二个样例中，没有任何票价区分配方式与地铁线路相匹配。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。