E) Wacky and his multiple ways

0

0 votes
Problem

You are given a graph with N vertices (numbered 1 to ) and M bidirectional edges, which doesn't contain multiple edges or self-loops — that is, the given graph is a simple undirected graph.

The i-th edge connects vertices ai and bi.

You have to print all vertices in sorted order which are present in at least one shortest path from a given source to a destination.

Input Format

  • The first line of input contains a single integer  , denoting the number of test cases. The description of  test cases follows.
  • The first line of each test case contains 2 space-separated integers,  and M.
  • The i-th of the next M lines contains 2 space-separated integers ai and bi, denoting a bidirectional edge between vertex ai and bi in the graph.
  • The last line of each test case contains 2 space-separated integers, u and vsource and destination respectively.

Output Format

For each test case, output the possible vertices in a single line.

Constraints

  • 1T1000
  • 2N200000
  • 0Mmin(N(N1)/2,200000)
  • 1ai,biN
  • The graph doesn't contain self-loops or multiple edges.

 

 

Sample Input
1
8 10
1 2
2 6
1 4
1 5
5 7
4 3
3 8
6 8
7 8
5 6
5 8
Sample Output
5 6 7 8
Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?