Avengers#10648
Nurlashko, Nurbakyt, and Zhora are the last warriors of an ancient ninja clan fighting against the tyranny of Emperor Ren. After a crushing defeat in open battle, they decided to split their army into three camps and switch to guerrilla warfare.
However, the absurd reforms of Emperor Ren imposed strict rules: the roads between cities can only be traveled in one direction. Moreover, the directions were chosen in such a way that it is impossible, after traversing several roads, to return to the original city.
Now the clan is deciding where to place their camps. The emperor's army regularly conducts raids, checking various routes. If, during one such raid, the enemy manages to capture all three camps, the clan will be unable to regroup and will lose the war. Your task is to help choose three cities so that there is no path passing through all of them.
The first line contains two integers n, m~(1 \le n, m \le 10^6) — the number of cities and roads in the empire.
The following lines each contain two integers v_i, u_i~(1 \le v_i, u_i \le n), describing a directed road from city v_i to city u_i.
Print three integers — the indices of the cities where the clan should place their camps. If no such triple of cities exists, print . If there are multiple solutions, you may output any of them.
Example 1
Example 2