#include <stdio.h>
#include <stdlib.h>
#define VISITED 1
#define UNVISITED 0

typedef struct node{

    int number_of_neighbours;
    int *neighbours;
    int *costs;

}AdjacencyList;


void addNeighbour(AdjacencyList **list, int node, int neighbour, int cost)
{
    if ((*list)[node].number_of_neighbours == 0)
    {
        (*list)[node].neighbours = (int *) calloc(1, sizeof(int));
        (*list)[node].costs = (int *) calloc(1, sizeof(int));
        (*list)[node].number_of_neighbours ++;
        (*list)[node].neighbours[(*list)[node].number_of_neighbours - 1] = neighbour;
        (*list)[node].costs[(*list)[node].number_of_neighbours - 1] = cost;

    }
    else
    {
        (*list)[node].number_of_neighbours ++;
        (*list)[node].neighbours = (int *) realloc((*list)[node].neighbours, (*list)[node].number_of_neighbours * sizeof(int));
        (*list)[node].costs = (int *) realloc((*list)[node].costs, (*list)[node].number_of_neighbours * sizeof(int));
        
        (*list)[node].neighbours[(*list)[node].number_of_neighbours - 1] = neighbour;
        (*list)[node].costs[(*list)[node].number_of_neighbours - 1] = cost;
    }
}

void DFS(AdjacencyList *list, int *visited, int currentNode)
{
    visited[currentNode] = VISITED;

    printf("%d \n", currentNode);

    for( int i = 0; i < list[currentNode].number_of_neighbours; i++)
    {
        if(visited[list[currentNode].neighbours[i]] == UNVISITED)
        {
            DFS(list, visited, list[currentNode].neighbours[i]);
        }
    }

}

void destroyAdjacencyList(AdjacencyList **list, int number_of_nodes)
{
    for(int i = 0; i <= number_of_nodes; i++)
    {
        if ((*list)[i].number_of_neighbours > 0)
        {
            free((*list)[i].neighbours);
            free((*list)[i].costs);
        }
    }
    free(*list);
}

int main()
{
    int numar_noduri, numar_muchii, nr = 0, x, y;
    
    FILE *read = fopen("dfs.in", "r");
    FILE *write = fopen("dfs.out","w");

    fscanf(read,"%d%d", &numar_noduri, &numar_muchii);
    int *visited = (int *) calloc(numar_noduri + 1, sizeof(int));
    AdjacencyList * list = (AdjacencyList *) calloc(numar_noduri + 1, sizeof(AdjacencyList));

    for(int i = 0; i < numar_muchii; i++)
    {
        fscanf(read, "%d%d", &x, &y);
        addNeighbour(&list, x, y, 0);
        addNeighbour(&list, y, x, 0);
    }

    for (int i = 1; i <= numar_noduri; i++)
    {
        if(visited[i] == UNVISITED) 
        {
            DFS(list, visited, i);
            nr++;
        }    
    }

    fprintf(write, "%d", nr);
    destroyAdjacencyList(&list, numar_noduri); 
    free(visited);
    return 0;
}