Question
The Journey from Cities A and B
In the Kingdom of Nodes, two cities—A and B—were chosen by the council.
Their task was simple:
“Find all cities that are at the same shortest distance from both A and B.”
The kingdom had n cities (0 to n−1), connected by m undirected roads of equal length.
Travelers could move between any two cities that shared a road.
Your job is to identify all cities that can be reached from both A and B in an equal minimum number of steps.
If no such city exists, print an empty list.
Input
First line: two integers n and m — number of cities and roads.
Next m lines: each has two integers u v, meaning there is a bidirectional road between cities u and v.
Final line: two integers A B — the starting cities of the two travelers.
Next m lines: each has two integers u v, meaning there is a bidirectional road between cities u and v.
Final line: two integers A B — the starting cities of the two travelers.
Output
Print all cities that are equally distant from both A and B, in any order. Return an empty list if none exist.
Example
Input :
4 4
0 1
0 2
2 3
1 3
0 3
Output:
1 2
Explanation:
City 1 is at a distance of 1 from both cities 0 and 3.
City 2 is also at a distance of 1 from both cities 0 and 3.
4 4
0 1
0 2
2 3
1 3
0 3
Output:
1 2
Explanation:
City 1 is at a distance of 1 from both cities 0 and 3.
City 2 is also at a distance of 1 from both cities 0 and 3.