← 返回题目列表

Codeforces · 666/B

B. 世界巡演

中文机器翻译题面 查看原题

著名雕塑家西加索进行世界巡演!

嗯,它实际上并不是一个世界范围的。但不是每个人都应该有机会看到雕塑家的作品,不是吗?否则就不会有任何排他性。因此西卡索的世界巡演将全部在他的祖国贝尔兰举行。

西加索非常专注于他的工作,他希望尽可能少地分心。因此他只会访问四个城市。这些城市都会有所不同,所以没有人会认为他有“最爱”。当然,为了省钱,他会选择这些城市之间最短的路径。但正如你可能已经猜到的那样,西加索是一个奇怪的人。虽然他不喜欢办展览,但他喜欢环游全国,欣赏风景。所以他希望他要旅行的总距离尽可能大。然而,雕塑家不善于计划,所以他向你寻求帮助。

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。