CF1322F 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$（$2 \le n \le 500\,000,\ 1 \le m \le 500\,000$），分别表示城市中的车站数量和地铁线路数量。 接下来的 $n-1$ 行，每行包含两个整数 $v_i$ 和 $u_i$（$1 \le v_i,\ u_i \le n$，$v_i \ne u_i$），表示一条连接 $v_i$ 和 $u_i$ 的双向隧道。保证任意两车站之间恰好有一条简单路径。 接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i,\ b_i \le n$，$a_i \ne b_i$），表示一条地铁线路。

第一行输出一个整数 $k$，表示所使用的最大票价区间。 第二行输出 $c_1, c_2, \ldots, c_n$（$1 \le c_i \le k$），表示每个车站的票价区间。 如果有多种方案，输出任意一种即可。如果无法分配票价区间，输出“-1”。

在第一个样例中，线路 $1 \rightarrow 3$ 依次经过车站 1、2、3。按照这个顺序，车站的票价区间递增。由于该线路包含 3 个车站，至少需要 3 个票价区间。因此答案 $1, 2, 3$ 是最优的。 在第二个样例中，无法分配票价区间使其与地铁线路一致。 由 ChatGPT 4.1 翻译