[AdditionalFile5488.zip](file://AdditionalFile5488.zip?type=additional_file)

#5488. 「COI 2022」Vinjete

标签: 传统 | 时间限制: 3000 ms | 内存限制: 512 MiB |

题目描述

译自 COI 2022 T4「Vinjete」

在阔别两年线上模式后，国际信息学奥林匹克竞赛（IOI）终于将要在线下举办。国际科学委员会（ISC）和国际技术委员会（ITC）一如既往地感到压力山大，选手们兴奋不已，家长们则既骄傲又紧张。但要说对这次现场活动最激动的人，非马尔纳先生莫属。他又可以品尝萨格勒布机场清晨的葡萄汁了，又可以品尝最顶级的亚洲美食了，又可以享受每日的短途旅行了。

你们当中经验更丰富的人会问自己：「什么短途旅行？！马尔纳先生几乎从不参加与其他代表团一起的集体旅行。」 你说得对，他确实不参加，他会在活动开始前几个月就计划好自己的专属旅行。

首先，他解决了所有租车的后勤问题，然后列出了一份包含 $N$ 个他想去的城市的简短清单。他在地图上圈出这些城市，并用高速公路将每对直接相连的城市连接起来。有趣的是，今年他正好画了 $N-1$ 条连接线，并意识到使用这些高速公路可以在任意两个城市之间找到一条路径。

这还不是全部，看来在亚洲，你能买到 $M$ 种不同的高速公路收费票（vignettes）。对于每条高速公路，都需要一个特定的收费票类型子集才能通行。马尔纳先生立即用从 $1$ 到 $M$ 的整数为所有不同的收费票类型建立了编号。更有趣的是，他设法用一种方式来编号，即要通过第 $i$ 条高速公路，你需要购买所有编号大于等于 $l_{i}$ 且小于等于 $r_{i}$ 的收费票。

同样地，他用从 $1$ 到 $N$ 的整数为所有城市建立了编号，其中本次奥赛的主办城市，印度尼西亚的日惹市（Yogyakarta）被标记为 $1$。

为了更好地规划路线，他决定请你编写一个程序，计算出对于每个城市，他从日惹出发到达该城市所需购买的最少收费票数量是多少。

输入格式

第一行包含题目描述中的整数 $N$ 和 $M$。

接下来的 $N-1$ 行中，第 $i$ 行包含 $a_{i}, b_{i}, l_{i}$ 和 $r_{i}$，表示第 $i$ 条高速公路连接着编号为 $a_{i}$ 和 $b_{i}$ $(1 \leq a_{i}, b_{i} \leq N, a_{i} \neq b_{i})$ 的城市，并且通过该高速公路需要购买编号在区间 $[l_{i}, r_{i}]$ $(1 \leq l_{i} \leq r_{i} \leq M)$ 内的收费票。

这些高速公路的连接方式保证了 $N$ 个城市中的任意两两之间都是连通的。

输出格式

输出应包含 $N-1$ 行，其中第 $i$ 行应包含马尔纳先生从日惹（编号为 $1$ 的城市）出发，到达编号为 $(i+1)$ 的城市所需购买的最少收费票数量。

样例 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

为了到达编号为 $2$ 的城市，你可以购买编号为 $(2,3,4)$ 的收费票。

为了到达编号为 $3$ 的城市，你可以购买编号为 $(1,2,3,4)$ 的收费票。

为了到达编号为 $4$ 的城市，你可以购买编号为 $(2,3,4,5)$ 的收费票。

为了到达编号为 $5$ 的城市，你可以购买编号为 $(2,3,4,5,6)$ 的收费票。

为了到达编号为 $6$ 的城市，你可以购买编号为 $(1,2,3,4)$ 的收费票。

样例 2

输入

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

输出

1
2
3
5

为了到达编号为 $2$ 的城市，你可以购买编号为 $2$ 的收费票。

为了到达编号为 $3$ 的城市，你可以购买编号为 $(2,3)$ 的收费票。

为了到达编号为 $4$ 的城市，你可以购买编号为 $(1,2,3)$ 的收费票。

为了到达编号为 $5$ 的城市，你可以购买编号为 $(1,2,3,4,5)$ 的收费票。

数据范围与提示

详细子任务附加限制及分值如下表所示：