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

#define MAX 20

// Node for adjacency list
typedef struct node {
    int vertex;
    struct node *next;
} NODE;

NODE *G[MAX];     // adjacency list heads
int visited[MAX]; // for DFS, BFS
int n;            // number of vertices

// Create new node
NODE* createNode(int v) {
    NODE *newNode = (NODE*)malloc(sizeof(NODE));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// Insert edge vi --> vj
void insertEdge(int vi, int vj) {
    NODE *temp = createNode(vj);

    if (G[vi] == NULL) {
        G[vi] = temp;
    } else {
        NODE *ptr = G[vi];
        while (ptr->next != NULL)
            ptr = ptr->next;
        ptr->next = temp;
    }
}

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

    NODE *ptr = G[v];
    while (ptr != NULL) {
        if (!visited[ptr->vertex])
            DFS(ptr->vertex);
        ptr = ptr->next;
    }
}

// BFS iterative
void BFS(int start) {
    int queue[MAX];
    int front = 0, rear = -1;

    for (int i = 0; i < n; i++)
        visited[i] = 0;

    visited[start] = 1;
    queue[++rear] = start;

    printf("BFS Traversal: ");

    while (front <= rear) {
        int v = queue[front++];
        printf("%d ", v);

        NODE *ptr = G[v];
        while (ptr != NULL) {
            if (!visited[ptr->vertex]) {
                visited[ptr->vertex] = 1;
                queue[++rear] = ptr->vertex;
            }
            ptr = ptr->next;
        }
    }
    printf("\n");
}

// MAIN PROGRAM — CONSTRUCTION + DFS + BFS
int main() {
    int edges, u, v, start;

    printf("Enter number of vertices: ");
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
        G[i] = NULL;

    printf("Enter number of edges: ");
    scanf("%d", &edges);

    printf("Enter edges (u v) as 0-based vertices:\n");
    for (int i = 0; i < edges; i++) {
        scanf("%d %d", &u, &v);
        insertEdge(u, v);
        insertEdge(v, u); // undirected graph
    }

    printf("\nEnter starting node for traversal: ");
    scanf("%d", &start);

    // DFS
    for (int i = 0; i < n; i++)
        visited[i] = 0;

    printf("DFS Traversal: ");
    DFS(start);
    printf("\n");

    // BFS
    BFS(start);

    return 0;
}