AC

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

const int MAXN = 1e3 + 10;
int n, m, s, T;
bool vis[MAXN];
vector<int> p[MAXN];
vector<int> res;
int sum;


void dfs(int x) {
	vis[x] = true;
	sum++;
	res.push_back(x);


	for (auto next : p[x]) {
		if (!vis[next]) {
			dfs(next);
			res.push_back(x);
		}
	}
}

int main() {

	cin >> T;
	while (T--) {
		cin >> n >> m >> s;

		for (int i = 1; i <= n; i++) {
			p[i].clear();
		}

		for (int i = 0; i < m; i++) {
			int u, v;
			cin >> u >> v;
			p[u].push_back(v);
			p[v].push_back(u);
		}


		for (int i = 1; i <= n; i++) {
			sort(p[i].begin(), p[i].end());
		}

		memset(vis, 0, sizeof(vis));
		res.clear();
		sum = 0;
		dfs(s);
		if (sum == n) {
			for (size_t i = 0; i < res.size(); i++) {
				cout << res[i] << " ";
			}
		} else {
			for (size_t i = 0; i < res.size(); i++) {
				cout << res[i] << " ";
			}
			cout << 0;
		}
		cout << endl;
	}

	return 0;
}