题目背景

译自 COCI 2024/2025 #5 T5。$\texttt{3.5s,0.5G}$。满分为 $120$。

题目描述

给定 $n$ 个节点的树，初始时所有边边权为 $0$。

$q$ 次操作，第 $i$ 次操作将 $u,v$ 最短路径上的边权覆盖为 $i$。

最终输出每条边的边权。

输入格式

第一行，正整数 $n,q$。

接下来 $(n-1)$ 行，每行两个正整数 $u_i,v_i$，描述第 $i$ 条树边 $(u_i,v_i)$。

接下来 $q$ 行，每行两个正整数 $u,v$，描述一次操作。

输出格式

一行 $(n-1)$ 个非负整数，第 $i$ 个整数描述第 $i$ 条树边的边权。

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

2 0 2 1 2

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

3 4 4 0

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

1 3 3 4

提示

数据范围

对于 $100\%$ 的数据，保证：

• $2\le n\le 10^6$；
• $1\le q\le 10^6$；
• $1\le u,v\le n$。

• 特殊性质 A：$u_i=i,v_i=i+1$。
• 特殊性质 B：$q\le 10^3$。