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

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

#include <iostream>

#include <queue>

using namespace std;

#define MAX 1001

 

int N, M, V;

int map[MAX][MAX];

bool visited[MAX];

queue<int> q;

 

void reset() 

{

    for (int i = 1; i <= N; i++) 

        visited[i] = 0;

}

 

void DFS(int v) 

{

    visited[v] = true;

    cout << v << endl;

    

    for (int i = 1; i <= N; i++) 

        if (map[v][i] == 1 && visited[i] == 0) 

            DFS(i);

}

 

void BFS(int v) 

{

    q.push(v);

    visited[v] = true;

    cout << v << endl;

 

    while (!q.empty()) 

    {

        v = q.front();

        q.pop();

        

        for (int w = 1; w <= N; w++) 

        {

            if (map[v][w] == 1 && visited[w] == 0) 

            {

                q.push(w);

                visited[w] = true;

                cout << w << endl;

            }

        }

    }

}

 

int main() 

{

    cin >> N >> M >> V;

 

    for (int i = 0; i < M; i++) 

    {

        int a, b;

        cin >> a >> b;

        map[a][b] = 1;

        map[b][a] = 1;

    }

 

    reset();

    DFS(V);

    

    cout << endl;

    

    reset();

    BFS(V);

 

    return 0;

}