← 返回题目列表

Codeforces · 1322/F

F. 分配票价

中文机器翻译题面 查看原题

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$$$) 来描述。可以保证任意两个站点之间都存在一条简单路径。

以下 $$$m$$$ 线路描述了另一条地铁线路。每行都用整数 $$$a_i$$$、$$$b_i$$$ ($$$1 \le a_i,\ b_i \le n$$$、$$$a_i \neq b_i$$$) 来描述。

输出

在第一行打印整数 $$$k$$$ — 使用的最大票价区域。

在下一行中打印整数 $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le k$$$) — 车站的票价区。

如果有多个可能的答案,请打印其中任何一个。如果无法分配票价区域,请打印“-1”。

示例

输入 #1

3 1
1 2
2 3
1 3

输出 #1

3
1 2 3

输入 #2

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

输出 #2

-1

输入 #3

7 5
3 4
4 2
2 5
5 1
2 6
4 7
1 3
6 7
3 7
2 1
3 6

输出 #3

-1

注意

在第一个示例中,$$$1 \rightarrow 3$$$ 线按顺序经过车站 1、2、3。按照此顺序,车站的票价区域逐渐增加。由于该线路有3个车站,因此至少需要3个收费区。所以答案1、2、3是最优的。

在第二个示例中,不可能分配与地铁线路一致的票价区域。