#P17803. [Ontak2024]ROZ

[Ontak2024]ROZ

题目描述

给定一个连通无向简单图,顶点编号 11 到 nn,边按输入顺序编号 11 到 mm。另外指定其中 n−1n-1 条边,保证它们构成一棵生成树 TT。

为所有边赋权,使权值序列

c(1),c(2),…,c(m)c(1),c(2),\ldots,c(m)

恰为 1,2,…,m1,2,\ldots,m 的一个排列,并使指定的 TT 成为图的最小生成树。

在所有满足条件的赋权中,求权值序列字典序最小的一个。比较的是按原边编号排列的权值。

输入格式

第一行两个整数 n,mn,m。

接下来 mm 行,第 ii 行两个整数 ui,viu_i,v_i,描述第 ii 条边。

最后一行包含 n−1n-1 个整数 r1,…,rn−1r_1,\ldots,r_{n-1},为指定生成树的边编号。

输出格式

输出一行 mm 个整数 c(1),…,c(m)c(1),\ldots,c(m)。

数据范围

  • 1≤n,m≤3000001\le n,m\le300000。
  • 1≤ui,vi≤n1\le u_i,v_i\le n,ui≠viu_i\ne v_i。
  • 无重边,原图连通。
  • 1≤ri≤m1\le r_i\le m,所列边组成连通的生成树。

样例 1

输入:

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

输出:

3 4 5 1 2

样例 2

输入:

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

输出:

1 4 2 3

子任务

编号 附加限制 分值
1 n,m≤9n,m\le9 8
2 n,m≤1000n,m\le1000 18
3 指定树是以顶点 11 为中心的星形树 9
4 指定树的边恰连接编号相邻的顶点,构成 1−2−⋯−n1-2-\cdots-n 12
5 n=mn=m 17
6 无附加限制 36