#214463. [JOISC 2019] 穿越时空 Bitaro / Bitaro, who Leaps through Time

Beaverland 由 座城市组成，编号从 到 。共有 条道路连接这些城市。第 条道路（）双向连接城市 和城市 。在 Beaverland，他们使用 Byou 作为时间单位。Beaverland 中的每一天长度为 Byous。每天从时刻 开始，到时刻 （）称为时间 。通过任意一条道路需要 Byou，且第 条道路每天仅能在时间 到 之间通行。具体而言，要通过第 条道路，必须在时间 （满足 ）从城市 或城市 出发，并在时间 到达另一座城市。

Bitaro 曾是 Beaverland 中一名普通的海狸。然而，为了应对他的迟到问题，他最终习得了“穿越时间”的技能。使用该技能一次，他可以回到 1 Byou 之前的时间。但他无法回到当天之前：如果他在时间 到 之间使用该技能，他将回到当天的时间 。他只能在位于某座城市时使用该技能。使用该技能不会改变 Bitaro 的位置。

Bitaro 在使用该技能时会感到疲惫。为了寻找使用该技能次数更少的旅行方式，他决定进行一个包含 步的思维实验。在思维实验的第 步（），他执行以下操作之一：

• 修改第 条道路的可通行时间段。修改后，该道路仅能在时间 到 之间通行。
• 假设他在时间 位于城市 ，计算到达城市 且时间为 的当天所需的最少技能使用次数。

他想知道该思维实验的结果。

请编写一个程序，输入 Beaverland 的城市数量、道路信息以及思维实验的细节，计算并输出该思维实验的结果。

从标准输入读取以下数据。输入中的所有值均为整数。

（Query 1）

（Query ）

此处，每个（Query ）由 4 或 5 个以空格分隔的整数组成。令 为其第一个整数。则：

• 若 ，（Query ）包含 4 个整数 、、 和 。这意味着，在思维实验的第 步中，第 条道路的可通行时间段被修改为从时间 到时间 。
• 若 ，（Query ）包含 5 个整数 、、、 和 。这意味着，在思维实验的第 步中，你的程序应在假设 Bitaro 在时间 位于城市 的前提下，计算在当天时间 到达城市 所需的最少技能使用次数。

对于每个满足 的步骤，按顺序在标准输出中输出一行，包含所需的最少技能使用次数。

样例输入 1

3 3
0 5
0 5
2 1 3 3 3
1 2 0 1
2 1 3 3 3

样例输出 1

2
4

样例输入 2

5 5
3 5
4 8
2 6
5 10
2 5 3 1 10
2 2 6 5 6
1 3 4 6
2 3 3 4 3
2 4 5 1 5

样例输出 2

4
3
2
3

样例输入 3

7 7
112103440 659752416
86280800 902409187
104535475 965602300
198700180 945132880
137957976 501365807
257419446 565237610
2 4 646977260 7 915994878
2 1 221570340 6 606208433
2 7 948545948 4 604273995
2 7 247791098 5 944822313
2 7 250362511 2 50167280
2 3 364109400 4 555412865
2 7 33882587 7 186961394

样例输出 3

145611455
0
447180143
0
207252171
0
0

样例输入 4

7 7
535825574 705426142
964175291 996597835
481817391 649559926
4519006 410772613
74521477 274584126
256535565 899389890
1 6 511428966 602601933
1 1 69986642 201421232
2 3 636443425 4 625975977
1 6 235225515 405336399
2 3 866680458 3 701821857
1 6 180606048 900533151
1 6 612564160 720179605

样例输出 4

10467449
164858601

样例 1 解释

在思维实验的第 1 步中，Bitaro 从城市 1 出发，用 1 Byou 移动到城市 2，再用 1 Byou 从城市 2 移动到城市 3，从而在时间 5 到达城市 3。因此，通过使用技能两次，他可以在时间 3 到达城市 3。

在思维实验的第 2 步中，第 2 条道路的可通行时间段被修改为从时间 0 到时间 1。

在思维实验的第 3 步中，Bitaro 从城市 1 出发，用 1 Byou 移动到城市 2，从而在时间 4 到达城市 2。然后，他使用技能四次，用 1 Byou 移动到城市 3，并等待 2 Byous，从而在时间 3 到达城市 3。

数据范围

• 。
• 。
• （）。
• （）。
• （，）。
• （，）。
• （，）。
• （，）。
• （，）。
• （，）。

子任务

1. （4 分），。
2. （30 分）（）。
3. （66 分）无额外约束。