#include <stdio.h>

#define MAX 502

typedef struct
{
    int x;
    int y;
} LocationPoint;

typedef struct
{
    LocationPoint data[MAX * MAX];
    int top;
} Stack;

int board[MAX][MAX] = {
    {1, 1, 1, 0, 1, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 1, 0, 0, 0, 0, 0},
    {1, 1, 1, 0, 1, 0, 0, 0, 0, 0},
    {1, 1, 0, 0, 1, 0, 0, 0, 0, 0},
    {0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

int n = 7, m = 10;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1}; // 상하좌우

int visit[MAX][MAX] = {0}; // 해당 칸 방문 여부를 저장

void initStack(Stack *s) // 스택의 top 값을 0으로 초기화
{
    s->top = 0;
}

void push(Stack *s, LocationPoint p)
{
    s->data[s->top++] = p;
}

int empty(Stack *s)
{
    return s->top == 0;
}

LocationPoint pop(Stack *s)
{
    return s->data[--s->top];
}

int main()
{
    Stack S;
    initStack(&S);

    visit[0][0] = 1;                 // 1. 알고리즘 시작 시 (0, 0) 방문 표시
    push(&S, (LocationPoint){0, 0}); // 2. 해당 칸을 스택에 넣는다.

    while (!empty(&S))
    {
        LocationPoint current = pop(&S); // 3. 초기 세팅 후 스택이 빌 때까지 스택의 top을 빼줌
        printf("(%d, %d) -> ", current.x, current.y);

        // 4. 해당 좌표의 상하좌우를 살펴보며 스택에 넣는다

        for (int dir = 0; dir < 4; dir++) // 상하좌우 살펴보기
        {
            int nX = current.x + dx[dir];
            int nY = current.y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감

            if (nX < 0 || nX >= n || nY < 0 || nY >= m) // 범위 밖일 경우 넘어감
                continue;
            if (visit[nX][nY] || board[nX][nY] != 1) // 이미 방문한 칸이거나 0인 경우
                continue;
            visit[nX][nY] = 1;                 // 조건에 걸리지 않는다면 방문 가능, 방문했음을 저장
            push(&S, (LocationPoint){nX, nY}); // 해당 좌표를 스택에 넣어줌
        }
    }

    return 0;
}

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1001
#define MAX_M 10001

int N, M, V;
int graph[MAX_N][MAX_N];
int visited[MAX_N];

// 큐 구현
typedef struct
{
    int items[MAX_M];
    int front;
    int rear;
} Queue;

void initQueue(Queue *q)
{
    q->front = -1;
    q->rear = -1;
}

int isEmpty(Queue *q)
{
    return q->front == -1;
}

void enqueue(Queue *q, int value)
{
    if (q->rear == MAX_M - 1)
        return;
    if (isEmpty(q))
        q->front = 0;
    q->rear++;
    q->items[q->rear] = value;
}

int dequeue(Queue *q)
{
    if (isEmpty(q))
        return -1;
    int item = q->items[q->front];
    q->front++;
    if (q->front > q->rear)
        initQueue(q);
    return item;
}

// DFS 구현
void dfs(int v)
{
    visited[v] = 1;
    printf("%d ", v);

    for (int i = 1; i <= N; i++)
    {
        if (graph[v][i] && !visited[i])
        {
            dfs(i);
        }
    }
}

// BFS 구현
void bfs(int start)
{
    Queue q;
    initQueue(&q);

    visited[start] = 1;
    enqueue(&q, start);

    while (!isEmpty(&q))
    {
        int v = dequeue(&q);
        printf("%d ", v);

        for (int i = 1; i <= N; i++)
        {
            if (graph[v][i] && !visited[i])
            {
                visited[i] = 1;
                enqueue(&q, i);
            }
        }
    }
}

int main()
{
    scanf("%d %d %d", &N, &M, &V);

    for (int i = 0; i < M; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a][b] = graph[b][a] = 1;
    }

    // DFS
    printf("DFS: ");
    dfs(V);
    printf("\n");

    // 방문 배열 초기화
    for (int i = 1; i <= N; i++)
        visited[i] = 0;

    // BFS
    printf("BFS: ");
    bfs(V);
    printf("\n");

    return 0;
}