#6. ‘OIER’ 来到 2077 年的穿越者们与他们的战争

‘OIER’ 来到 2077 年的穿越者们与他们的战争

题目背景

O 为什么会在 Y 后面?

题目描述

最后灰姑娘计划在里泰尔德剧院开启的那一刻,OIER 的机动小队也开始了他们的行动。

他们打算首先传送到起点,然后占领整个爱丽丝树[1],而最重要的目标就是到达编号为 TT 的核心结点。然而经过拓扑结构的转换,爱丽丝树已经变成了它的商空间——一条链,而且在它之上的行动也变得异常不稳定。

经过研究他们发现,这条链上依然有 nn 个结点[2],他们将这些结点按顺序用 1,2,,n1,2,\dots,n 重新编号。然而,从编号为 ii的结点出发,一个单位时间内仅能够到达编号为[Li,Ri][L_i,R_i]的结点。不仅如此,爱丽丝树上的时间变得离散,以至于将从SS 出发视为第零个时刻,每一个正整数时刻他们都会被强制传送;在编号为 ii 的结点时会被传送到编号为 aia_i 的结点,传送可以看作瞬间进行。被传送一次之后,这个时刻他们就不会再次被传送。

就在机动小队计算出行动计划之后,不幸的事情发生了——他们的起点信息也因为拓扑结构陷入混乱,也就是说,他们将有可能从任何一个结点出发。

机动小队的作战将是灰姑娘掌控全城的一个重要环节,因此不能有失。你必须要计算出从每个结点出发到达 TT 的最短时间。注意,只有传送之后的到达才被看作有效。

数据格式与约定

输入

输入第一行包含 22 个整数 n,T(1Tn105)n,T(1 \le T \le n \le 10^5),表示结点个数和目标地点。

接下来 nn 行,每行包含 33 个整数 Li,Ri,ai(i=1,2,3,,n,i,1LiRin,1ain)L_i,R_i,a_i(i=1,2,3,\dots,n,\forall i,1 \le L_i\le R_i \le n,1\le a_i\le n),表示从 ii 出发,经过一个单位时间能够到达编号为[Li,Ri][L_i,R_i]的结点;而在正整数时刻到达 ii 时会被传送至 aia_i

输出

输出包含 nn 行,每行一个整数 ansians_i,表示从结点 ii 到达 TT 的最小时间;如果从这个结点无论如何也无法到达 TT,该行输出 1-1

样例

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

后记

2077 年 2 月 1 日。赛博朋克依旧没有到来。

里泰尔德的夜晚是黏稠的,黑暗被随处可见的泛光灯侵蚀,却又裹挟着这俗套至极的处处喧嚣。55 年过去,没有彻底的两极分化,没有绝望的 high tech low life,但散落在这个城市的,是那些曾经在小说里一次次出现、一遍遍重复的情节。

……你说 OIER?他们连来过的痕迹都没有留下。没有人记得他们。

里泰尔德剧院已经没有人了。除了常明的安全灯,没有任何一处还存在光芒。

安全灯之下,有一张小小的纸条。纸条大概是从日记本上撕下来的,纸张的颜色是染料染成的黄。上面只留着一行小字:

"Mans' cHarAdes is LeukeMia unfit' stanZa."


这就是他们的故事了。他们倾尽全力也没能改变的,一个俗套的故事。——不仅没改变故事,也没改变自己。

那么,现在,我们是不是应该聊聊……你的故事?


  1. 爱丽丝树的定义参见上一题,但对本题来说并不重要。 ↩︎

  2. 严格意义上商空间会使结点数也减少,但潘达最后的魔法让这个商空间仍然有nn个结点。 ↩︎