#include "stdafx.h"
#include <iostream>

void creatematrix(int **p,int n)
{
    for (int i=0; i<n;i++)
    {
        p[i] = new int[n];
    }

    //инициализация матрицы смежности
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
        {
            p[i][j] = 0;
        }
    }
}

void showmatrix(int **p, int n)
{
    //вывод матрицы смежности
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
            std::cout<<p[i][j]<<"  ";
            std::cout<<std::endl;

    }
}

void delmatrix(int **p, int n)
{
    for (int i = 0; i < n; i++)
        delete [] p[i];
}

void DFS(int **AdjacencyMatrix, int start, bool *visited, int finish,int n,int ccNum, int *cc)
{


    if (visited[start] != false) return;

    visited[start] = true;

    if (visited[finish] == true)
    {
        return;
    }

    cc[start] = ccNum;

    for (int i=0; i<n; i++)
    {
        if ((AdjacencyMatrix[start][i]!=0) && (!visited[i]))
            DFS(AdjacencyMatrix, i, visited, finish, n, ccNum,cc);
    }


}

int FindCCnum(int **AdjacencyMatrix, int start, bool *visited, int finish,int n, int *cc)
{
    int ccNum = 0;

     for (int i = 0; i < n; i++) // перебираем вершины
     {
         if (!visited[i]) // если текущая не помечена
         {
             ccNum++; // значит мы нашли компоненту связности
             DFS(AdjacencyMatrix,i,visited,finish,n, ccNum, cc); // запускаем на ней DFS

         }
     }

    return ccNum;
}

int main()
{
    int n,m;
    std::cin>>n>>m;

    //матрица смежности nxn
    int **AdjacencyMatrix = new int*[n];
    creatematrix(AdjacencyMatrix,n);

    int left, right;

    while (m>0)
    {
            std::cin>>left>>right;
            AdjacencyMatrix[left-1][right-1] = 1;
            AdjacencyMatrix[right-1][left-1] = 1;
    m--;
    }

    int start;
    int finish;

    //std::cin>>start>>finish;

    bool *visited = new bool[n];
    for (int i=0; i<n; i++)
    {
        visited[i] = false;
    }

    int ccnumber = 0;

    int *cc = new int[n];// сс[v] = номер компоненты, к которой принадлежит v
    for (int i=0; i<n; i++)
    {
        cc[i] = 0;
    }

    ccnumber = FindCCnum(AdjacencyMatrix,0,visited,n-1,n,cc);

    //showmatrix(AdjacencyMatrix,n);

    //DFS(AdjacencyMatrix, start-1,visited, finish-1,n);

    //if (visited[finish-1]==1) std::cout<<"1\n";
    //if (visited[finish-1]==0) std::cout<<"0\n";

    std::cout<<"ccnumber= "<<ccnumber<<std::endl;

    delmatrix(AdjacencyMatrix, n);


    system ("pause");
    return 0;
}