#include <fstream>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

class Algorithms
{
public:
    static void DFS( const vector<vector<int>>& adjacencyList, int startNode, vector<bool>& visited )
    {
        stack<int> nodes;
        nodes.push( startNode );  // adaugam nodul de start in stiva

        while( !nodes.empty() ) {
            // scoatem varful stivei
            int crtNode = nodes.top();
            nodes.pop();

            if( visited[crtNode] )  // se poate sa fi vizitat deja nodul (un nod poate aparea de 2 ori in stiva)
                continue;

            visited[crtNode] = true;  // vizitam nodul
            // bagam vecinii nevizitati in stiva
            for( auto node : adjacencyList[crtNode] ) {
                if( !visited[node] )
                    nodes.push( node );
            }
        }
    }

    static void BFS( const vector<vector<int>>& adjacencyList, int startNode, vector<int>& distance )
    {
        queue<pair<int, int>> nodes;     // retinem si nodul si distanta fata de start
        nodes.push( { startNode, 0 } );  // adaugam nodul de start in coada
        distance[startNode] = 0;         // vizitam nodul de start

        while( !nodes.empty() ) {
            // scoatem primul nod din coada
            int crtNode = nodes.front().first, crtDistance = nodes.front().second;
            nodes.pop();

            // bagam vecinii nevizitati in coada
            for( auto node : adjacencyList[crtNode] ) {
                if( distance[node] == -1 ) {
                    distance[node] = crtDistance + 1;  // vizitam vecinul
                    nodes.push( { node, distance[node] } );
                }
            }
        }
    }
};

void solveDFS()
{
    int      N, M;
    ifstream in( "dfs.in" );
    in >> N >> M;
    vector<vector<int>> adjacencyList( N + 1 );

    int x, y;
    for( int i = 0; i < M; ++i ) {
        in >> x >> y;
        adjacencyList[x].push_back( y );
        adjacencyList[y].push_back( x );
    }

    int          nrComponents = 0;
    vector<bool> visited( N + 1 );
    ofstream     out( "dfs.out" );
    for( int startNode = 1; startNode <= N; ++startNode )
        if( !visited[startNode] ) {
            ++nrComponents;
            Algorithms::DFS( adjacencyList, startNode, visited );
        }

    out << nrComponents;
}

void solveBFS()
{
    int      N, M, S;
    ifstream in( "bfs.in" );
    in >> N >> M >> S;
    vector<vector<int>> adjacencyList( N + 1 );

    int x, y;
    for( int i = 0; i < M; ++i ) {
        in >> x >> y;
        adjacencyList[x].push_back( y );
    }

    vector<int> distance( N + 1, -1 );
    ofstream    out( "bfs.out" );
    Algorithms::BFS( adjacencyList, S, distance );
    for( int i = 1; i <= N; ++i ) {
        out << distance[i] << ' ';
    }
}

int main()
{
    solveDFS();
}