# 백준 1260번 DFS와 BFS

## Solution

import sys
from collections import deque

n, m, v = map(int, input().split())

graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)

for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)

for i in range(1, n + 1):
graph[i].sort()

def dfs(start):
visited[start] = True
print(start, end=' ')
for i in graph[start]:
if not visited[i]:
dfs(i)

def bfs(start):
queue = deque([start])
visited[start] = True

while queue:
now = queue.popleft()
print(now, end=' ')
for i in graph[now]:
if not visited[i]:
queue.append(i)
visited[i] = True

dfs(v)
visited = [False] * (n + 1)
print()
bfs(v)
import sys
from collections import deque
n, m, V = list(map(int, si().split()))
adj = [[] for _ in range(n + 1)]

for _ in range(m):
x, y = list(map(int, si().split()))

for i in range(1, n + 1):

visit = [0] * (n + 1)
def dfs(x):
visit[x] = 1
print(x, end=' ')
if visit[y]:
continue
dfs(y)

def bfs(x):
visit = [0] * (n + 1)
queue = deque()
queue.append(x)
visit[x] = 1
while queue:
x = queue.popleft()
print(x, end=' ')
bfs(V)