10648. Avengers

 

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.

 

Input. 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 vi, ui (1 ≤ vi, ui ≤ n), describing the directed road from vi to ui.

 

Output. 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.

 

Sample input 1

Sample output 1

3 2

1 2

2 3

-1

 

 

Sample input 2

Sample output 2

3 2

1 2

1 3

2 3 1

 

 

SOLUTION

graphs - topological sort

 

Algorithm analysis

In the graph, you need to find any three vertices that do not lie on the same path.

Let’s start Kahn’s algorithm for topological sort. Find two vertices that will be in the queue at the same time. In this case, there is no path where these two vertices lie. Adding any third vertex to them, we get the answer.

If, when implementing the Kahn algorithm, the queue always contains at most one vertex, then all the vertices of the graph lie on the same path. And it means that topological sort is unique.

 

Example

The graphs from the test cases have the form:

In the first example, all three vertices lie on the same path. In the second example, three vertices do not lie on the same path.

 

Algorithm realization

Declare the data structures. Store the input graph in the adjacency list g. Store the incoming degrees of the vertices in the array InDegree.

 

vector<vector<int> > g;

vector<int> InDegree;

deque<int> q;

 

Read the input data.

 

scanf("%d %d", &n, &m);

g.resize(n + 1);

InDegree.resize(n + 1);

for (i = 0; i < m; i++)

{

  scanf("%d %d", &a, &b);

  g[a].push_back(b);

 

For each edge (a, b) increase InDegree[b] by 1.

 

  InDegree[b]++;

}

 

All vertices which degrees equals to zero, insert to the queue q.

 

for (i = 1; i < InDegree.size(); i++)

  if (InDegree[i] == 0) q.push_back(i);

 

Save the required three vertices in x, y, z.

 

x = y = -1;

 

Continue the algorithm until the queue q is empty.

 

while (!q.empty())

{

 

If the queue contains more than one vertex, the answer is found.

 

  if (q.size() > 1)

  {

    x = q[0];

    y = q[1];

    break;

  }

 

Extract the vertex v from the queue (it will be current in topological order).

 

  v = q.front(); q.pop_front();

 

Remove the edges (v, to) from the graph. For each such edge decrease the input degree of the vertex to. If the degree of the vertex to becomes zero, push it to the queue.

 

  for (int to : g[v])

  {

    InDegree[to]--;

    if (InDegree[to] == 0) q.push_back(to);

  }

}

 

Kahn’s algorithm is complete. If x is still -1, there is no solution.

 

if (x == -1)

  printf("-1\n");

else

{

 

Solution exists. For z we choose the minimum vertex that is not equal to x and y.

 

  z = 1;

  while (z == x || z == y) z++;

    printf("%d %d %d\n", x, y, z);

}