著名雕塑家西加索进行世界巡演!
嗯,它实际上并不是一个世界范围的。但不是每个人都应该有机会看到雕塑家的作品,不是吗?否则就不会有任何排他性。因此西卡索的世界巡演将全部在他的祖国贝尔兰举行。
西加索非常专注于他的工作,他希望尽可能少地分心。因此他只会访问四个城市。这些城市都会有所不同,所以没有人会认为他有“最爱”。当然,为了省钱,他会选择这些城市之间最短的路径。但正如你可能已经猜到的那样,西加索是一个奇怪的人。虽然他不喜欢办展览,但他喜欢环游全国,欣赏风景。所以他希望他要旅行的总距离尽可能大。然而,雕塑家不善于计划,所以他向你寻求帮助。
Berland有n个城市和m条单向道路。你必须选择西加索将访问的四个不同的城市,并确定他访问它们的顺序。因此,如果他按照您的顺序访问城市,从列表中的第一个城市开始,到最后一个城市结束,每次选择一对城市之间的最短路线,那么他将行驶的总距离将是最大的。
请注意,中间路线可能会经过分配给该旅游的城市,也可能会两次经过同一城市。例如,游览可以如下所示:$$\overline { 1 }, 2, 3, 4, \overline { 5 }, 4, 3, \overline { 2 }, 3, \overline { 4 }$$。四个城市按访问顺序标记为上划线:[1,5,2,4]。
请注意,柏林是一个高科技国家。因此,使用纳米技术,所有道路都被改变,使其具有相同的长度。出于同样的原因,使用普通汽车出行在该国并不是很流行,并且可能会出现这样的一对城市,其中一个城市通常无法从另一个城市乘汽车到达。然而,西加索非常保守,没有汽车就不能出行。选择城市,以便雕塑家可以仅使用汽车进行游览。保证它总是可以做到的。
输入
第一行有一对整数 n 和 m (4 ≤ n ≤ 3000, 3 ≤ m ≤ 5000) — Berland 的多个城市和单向道路。
接下来的 m 行中的每一行都包含一对整数 ui, vi (1 ≤ ui, vi ≤ n) — 从城市 ui 到城市 vi 的单向道路。请注意,ui 和 vi 不需要不同。此外,它可以是同一对城市之间的多条单向道路。
输出
打印四个整数 — Cicasso 根据最佳路线选择将访问的城市数量。城市编号应按照西加索访问的顺序打印。如果有多个解决方案,请打印其中任何一个。
示例
输入 #1
8 9 1 2 2 3 3 4 4 1 4 5 5 6 6 7 7 8 8 5
输出 #1
2 1 8 7
注意
设 d(x, y) 为城市 x 和 y 之间的最短距离。那么在示例中 d(2, 1) = 3、d(1, 8) = 7、d(8, 7) = 3。总距离等于 13。