1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

import sys

from collections import deque

 

 

def dfs(graph, v, visited):

    visited[v] = True

    print(v, end=‘ ‘)

 

    for i in graph[v]:

        if not visited[i]:

            dfs(graph, i, visited)

 

 

def bfs(graph, start, visited):

    queue = deque([start])

    visited[start] = True

 

    while queue:

        v = queue.popleft()

        print(v, end=‘ ‘)

        for i in graph[v]:

            if not visited[i]:

                queue.append(i)

                visited[i] = True

 

 

n, m, f = map(int, sys.stdin.readline().rstrip().split())

 

arr = [[] for _ in range(n + 1)]

 

for _ in range(m):

    a, b = map(int, sys.stdin.readline().rstrip().split())

    arr[a].append(b)

    arr[b].append(a)

 

for i in range(n + 1):

    arr[i].sort()

 

vArr1 = [False] * (n + 1)

vArr2 = [False] * (n + 1)

 

dfs(arr, f, vArr1)

print()

bfs(arr, f, vArr2)