Topological sort


NurlashKo, Nurbakyt, and Zhora are members of the last ninja clan fighting against even emperor Ren’swild reign. After devastating defeat in an open battle, they decided split their army into three camps and wage a guerrilla war.

One Emperor Ren’s ridiculous reforms allows to pass roads between cities only in one direction. Also, he chose the allowed directions of the roads in such way, so that it’s impossible to start and return to the same city after passing several roads.

Right now, the clan is deciding where to place their camps. Emperor Ren’s army makes regular raids inspecting some path. If Army crushes all three of the camps during their raid, clan wouldn’t be able to regroup and would loose the war. Help the clan to choose three cities, so that there is no path that passes through all three of these cities.


First line contains two numbers n, m (1n, m106) – number of cities and roads in the Empire. Next m contain pairs of numbers vi, ui (1vi, uin), describing the directed road from vi to ui.


Print three numbers, indexes of cities where the clan should place their camps. If there are no such three cities, print -1. If there are many answers, print any of them.


Time limit 2 seconds
Memory limit 128 MiB
Input example #1
3 2
1 2
2 3
Output example #1
Input example #2
3 2
1 2
1 3
Output example #2
2 3 1
Source 2021 KBTU Open, Spring Kazakhstan, Alma-Ata, May 30, Problem K