First, we claim the following proposition:

In a simple undirected graph \(G\), given vertices \(u\) and \(v\) and a vertex set \(S\), the following are equivalent: that it is reachable from \(u\) to \(v\) without visiting vertices in \(S\) (= there exists a (not necessarily simple) path from \(u\) to \(v\) not containing vertices in \(S\)), and that there exists a simple path from \(u\) to \(v\) that does not contain vertices in \(S\).

It is obvious that if “there exists a simple path from \(u\) to \(v\) that does not contain vertices in \(S\),” then “it is reachable from \(u\) to \(v\) without visiting vertices in \(S\).” We prove the converse.
This is true because, given a (not necessarily simple) path \(P=(P_1,P_2,\ldots, P_{\lvert P\rvert})\) from \(u\) to \(v\), one can obtain a simple path by performing the following operation for \(k=1,2,\ldots,N\):

• If vertex \(k\) occurs at most once in \(P\), do nothing.
• If vertex \(k\) occurs multiple times in \(P\), replace \(P\) with a new path obtained by concatenating the path from vertex \(u\) to the first occurrence of \(k\), and the path from the last occurrence of vertex \(k\) to vertex \(v\).

Since each step never increases the number of occurrences of each vertex in the path, and vertex \(k\) is made occur at most once in after the step for that vertex, so the final path \(P\) becomes a simple path from vertex \(u\) to vertex \(v\).

Next, we consider how to take route (choose the next vertex to advance) to travel from \(U\) to \(V\) on the lexicographically smallest simple path.

The first vertex vertex \(U\). For a vertex \(x\) adjacent to \(U\), there exists a simple path \(P\) toward \(V\) such that \(P_1=U\) and \(P_2=x\) if and only if there exists a simple path from \(x\) to \(V\) not containing \(U\); by the proposition above, this holds if and only if it is reachable from \(x\) to \(V\) without passing through \(U\). Hence, the next path after vertex \(U\) in the answer path is necessarily a vertex \(x\) adjacent to \(U\), and such that it is reachable from \(V\) to \(x\) without visiting \(U\). Conversely, in the answer path, the next vertex after \(U\) is the one with the smallest vertex number among such vertices. This is because, if there exists a simple path \(P\) toward \(V\) with \(P_1=U\) and \(P_2=x\), then for any simple path \(P'\) toward \(V\) with \(P'_1=U\), \(P'_2=x'\) \((x<x')\), the path \(P\) is lexicographically smaller than the path \(P'\).

Likewise, the simple path can be determined greedily until reaching \(V\) (until you find \(P_k=V\) for some \(k\)). In other words, when we know \(P_1,P_2,\ldots,P_k\), we can determine \(P_{k+1}\) as the vertex \(x\) with the minimum vertex number, among those adjacent to \(P_{k+1}\), and those reachable from \(V\) without passing through \(P_1,P_2,\ldots,P_k\).
Since the same vertex is not chosen, this operation terminates after a finite number of iterations. Also, due to how we choose vertices, there is always a vertex that can be chosen as \(P_{k+1}\). This way, the problem can be solved.

For each test case, the time complexity can be estimated as follows: Enumerating the vertices reachable from \(V\) without visiting \(P_1,P_2,\ldots,P_k\) takes \(O(N+M)\) time using, for example, DFS (Depth-First Search). Since \(k\) ranges from \(1\) to \(N-1\), so the overall time complexity is \(O(N(N+M))\). In an entire input file also, we have \(\Sigma_iN_i(N_i+M_i)\leq (\Sigma_iN_i)((\Sigma_iN_i)+(\Sigma_iM_i))\), so this algorithm is fast enough under the constraints of this problem.
Therefore, the problem has been solved.

Sample code in C++:

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < n; ++i)
#define N 1000

int n,m,x,y;
vector<int>e[N];
vector<int>ans;
bool used[N];
bool cand[N];

void dfs(int k){
	cand[k]=true;
	int sz=e[k].size();
	rep(i,sz){
		if((!cand[e[k][i]])&&(!used[e[k][i]]))dfs(e[k][i]);
	}
	return;
}

void solve(void){
	ans.clear();
	int cur = x;
	while(cur!=y){
		ans.push_back(cur);
		used[cur]=true;
		rep(i,n)cand[i]=false;
		dfs(y);
		int sz=e[cur].size();
		int nxt=n;
		rep(i,sz)if(cand[e[cur][i]])nxt=min(nxt,e[cur][i]);
		cur=nxt;	
	}
	ans.push_back(y);
	return;
}


int main(void){
	int t;
	cin >> t;
	rep(_,t){
		cin >> n >> m >> x >> y;
		x--,y--;
		rep(i,n)used[i]=false;
		int u,v;
		rep(i,m){
			cin >> u >> v;
			e[u-1].push_back(v-1);
			e[v-1].push_back(u-1);
		}
		solve();
		int sz = ans.size();
		rep(i,sz-1)cout << (ans[i]+1) << " ";
		cout << (ans[sz-1]+1) << endl;
		rep(i,n)e[i].clear();
	}
	return 0;
}