题目背景

译自 HIO (COI) 2022 T4。

题目描述

Gospodin Malnar 计划在亚洲旅行，访问 $N$ 个城市。这些城市通过 $N-1$ 条双向高速公路连接，形成一棵树。城市编号为 $1$ 到 $N$，起点为 $1$。

亚洲有 $M$ 种不同类型的通行证，编号从 $1$ 到 $M$。每条高速公路 $i$ 需要购买编号在 $[l_i,r_i]$ 范围内的所有通行证才能通过，第 $i$ 条公路连接 $a_i,b_i$ 两点。

你的任务是确定从起点到其他城市 $i$ $(2 \leq i \leq N)$ 所需购买的最少通行证数量。

输入格式

第一行包含两个整数 $N$ 和 $M$，表示城市数和通行证种类数。

接下来 $N-1$ 行，每行包含四个整数 $a_i, b_i, l_i, r_i$，表示一条高速公路及其所需通行证区间。

输出格式

输出 $N-1$ 行，第 $i$ 行表示从城市 $1$ 到城市 $i+1$ 所需的最少通行证数量。

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

3
4
4
5
4

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

1
2
3
5

提示

【样例解释】

样例 $1$：

• 到城市 $2$ 的路径覆盖区间 $[2,4]$，需 $3$ 个通行证 $(2,3,4)$。
• 到城市 $3$ 的路径覆盖 $[1,4]$，需 $4$ 个。
• 到城市 $4$ 的路径合并 $[2,4]$ 和 $[3,5]$，结果为 $[2,5]$，需 $4$ 个 $(2,3,4,5)$。
• 到城市 $5$ 的路径包含 $[2,4]$ 和 $[5,6]$，合并后需 $5$ 个。
• 到城市 $6$ 的路径合并 $[1,4]$ 和 $[2,3]$，结果为 $[1,4]$，需 $4$ 个。

样例 $2$：

• 到城市 $2$ 只需区间 $[2,2]$，$1$ 个通行证。
• 到城市 $3$ 合并 $[2,2]$ 和 $[3,3]$，共 $2$ 个。
• 到城市 $4$ 需合并 $[2,2]$, $[3,3]$, $[1,1]$，总覆盖 $[1,3]$，需 $3$ 个。
• 到城市 $5$ 的路径覆盖 $[1,5]$，需 $5$ 个。

【数据规模与约定】

对于所有数据，满足 $1 \leq N \leq 10^5$,$1 \leq M \leq 10^9$,$1 \leq a_i, b_i \leq N$, $1 \leq l_i \leq r_i \leq M$，且道路构成一棵树。

子任务编号	分值	附加限制
$1$	$11$	$N \leq 10^3$, $M \leq 10^3$
$2$	$13$	$N \leq 10^3$, $M \leq 10^9$
$3$	$16$	$N \leq 5 \times 10^4$, $M \leq 5 \times 10^4$
$4$	$29$	$N \leq 10^5$, $M \leq 10^5$
$5$	$31$	$N \leq 10^5$, $M \leq 10^9$