Let G be an undirected graph with nodes {0,...,n − 1} in which every node has degree at least one. One particle is located at a node u and another at node v. At each step, each particle can move to a node that is adjacent to the node it is currently at. The particle cannot remain at the same node, and since degree is at least one, there is always an adjacent node to which it can move. The particle can come back to the same node any number of times.
In the first part of the problem, you have to determine whether it is possible for the particles to move in such a way that after some finite number of steps, both are at the same node. The particles must meet at a common node, just crossing each other on the same edge is not sufficient.
In the second part of the problem, if it is possible for them to meet, you have to find the minimum number of steps after which they can meet, and all the possible nodes at which they can meet after minimum number of steps.
Input/Output: The first line of input contains 4 numbers, separated by a space, n,m,u,v. Here n is the number of nodes, m is the number of edges, u and v the numbers of the nodes at which the particles are initially located. Assume 2 ≤ n ≤ 105, (n + 1)/2 ≤ m ≤ 106, 0 ≤ u,v < n. The next m lines give the edges in the graph, with each line containing the two nodes with which the edge is incident. It can be assumed the graph has no self-loops or multiple edges, and every node has degree at least one. The first line of output should be the string “possible” if it is possible for the particles to meet, otherwise print “impossible”. If it is possible, the second line should give the minimum number of steps after which the particles can meet, and the third line should give the list of nodes in increasing order, at which they can meet, in minimum number of steps.
Sample Input 1 Sample Output 1
4 4 0 1 impossible
0 1
1 2
2 3
0 3
Sample Input 2 Sample Output 2
7 7 0 3 possible
0 1 4
1 2 5 6
1 4
2 3
4 5
4 6
5 6
Submission: Submit a single file named RollNo 11.cpp.
Homework: Do the same problem if the graph is directed.
1
