1260번
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
vector<int> vec[1001];
bool visit[1001];
void sorting(int n) {
for (int i = 1;i <= n;i++) {
sort(vec[i].begin(), vec[i].end());
}
}
void dfs(int n) {
visit[n] = true;
cout << n << " ";
for (int i = 0;i < vec[n].size();i++) {
if (!visit[vec[n][i]]) {
dfs(vec[n][i]);
}
}
}
void bfs(int n) {
queue<int> que;
visit[n] = true;
que.push(n);
while (!que.empty()) {
n = que.front();
que.pop();
cout << n << " ";
for (int i = 0;i < vec[n].size();i++) {
if (!visit[vec[n][i]]) {
que.push(vec[n][i]);
visit[vec[n][i]] = true;
}
}
}
}
int main() {
int n, m, v;
cin >> n >> m >> v;
int point1, point2;
for (int i = 0;i < m;i++) {
cin >> point1 >> point2;
vec[point1].push_back(point2);
vec[point2].push_back(point1);
}
sorting(n);
dfs(v);
memset(visit, false, sizeof(visit));
cout << endl;
bfs(v);
}