2021 KBTU Open, Spring Kazakhstan, Alma-Ata, May 30
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 to 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 lose 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 (1 ≤ n, m ≤
106) – number of cities and roads in the Empire. Each of the next m lines contains pair of numbers
ui (1 ≤
ui ≤ n), describing the directed road from
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.
3 2 1 2 2 3
3 2 1 2 1 3
2 3 1