#include <stdio.h>
#include <stdlib.h>
 
// Structure for adjacency list node
struct Node {
    int vertex;
    struct Node* next;
};
 
// Structure for the graph
struct Graph {
    int vertices;
    struct Node** adjLists; // array of pointers to linked lists
};
 
// Create a new adjacency list node
struct Node* createNode(int v) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}
 
// Create a graph with given vertices
struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->vertices = vertices;
 
    // Create an array of adjacency lists
    graph->adjLists = (struct Node**)malloc(vertices * sizeof(struct Node*));
 
    // Initialize each adjacency list as empty
    for (int i = 0; i < vertices; i++)
        graph->adjLists[i] = NULL;
 
    return graph;
}
 
// Add an edge (undirected)
void addEdge(struct Graph* graph, int src, int dest) {
    // Add edge from src to dest
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
 
    // Add edge from dest to src (because undirected)
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}
 
// Print adjacency list representation
void displayGraph(struct Graph* graph) {
    printf("\nAdjacency List Representation:\n");
    for (int i = 0; i < graph->vertices; i++) {
        struct Node* temp = graph->adjLists[i];
        printf("Vertex %d:", i);
        while (temp) {
            printf(" -> %d", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}
 
// Main function
int main() {
    int vertices, edges;
    printf("Enter number of vertices: ");
    scanf("%d", &vertices);
 
    struct Graph* graph = createGraph(vertices);
 
    printf("Enter number of edges: ");
    scanf("%d", &edges);
 
    printf("Enter edges (u v):\n");
    for (int i = 0; i < edges; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        addEdge(graph, u, v);
    }
 
    displayGraph(graph);
 
    return 0;
}