#include <bits/stdc++.h>

using namespace std;

const int N= 100010;

class Graf
{
private:
    int noduri , muchii;

    void dfs(int start,vector<int> v[N], vector<int> &viz);


    public:
    Graf(int,int);
    void add_edge(int x, int y);
    int nr_connected_components(vector<int> v[N], vector<int> &viz);
    void bfs(ifstream &, ofstream &,queue<pair<int,int>>, vector<int>*,vector<int>&,vector<int>&,int);
};

void Graf::bfs(ifstream &fin, ofstream &fout,queue<pair<int,int>> q,vector<int> adj[N], vector<int> &viz,vector<int> &ans,int nod_cerut)
{
    while(!q.empty())
    {
        pair<int,int> dp = q.front();
        int x = dp.first;
        int y = dp.second;
        ans[x] = y;
        for(auto it: adj[x])
            if(!viz[it])
            {
                viz[it] = 1;
                q.push(make_pair(it,y+1));
            }
        q.pop();
    }

    for(int i=1;i<=this->noduri;i++)
    {
        if(ans[i] == 0 && i != nod_cerut)
            ans[i] = -1;
        fout<<ans[i]<<" ";
    }
}

Graf::Graf(int n, int m)
{
    (*this).noduri = n;
    (*this).muchii = m;

    cout<<"Constructor " << n<<" "<<m<<'\n';
}

void Graf::dfs(int start, vector<int> v[N], vector<int> &viz)
{
    viz[start] = 1;
    for(auto it : v[start])
        if(!viz[it])
            dfs(it,v,viz);
    
}

int Graf::nr_connected_components(vector<int> v[N], vector<int> &viz)  {
    int ct=0;
    for(int i=1;i<=(this->noduri);i++)
        if(!viz[i]){
            dfs(i,v,viz);
            ct++;
        }
    return ct;
}



int main()
{
    int problema = 2;
    if(problema == 2)
    {
        ifstream fin("bfs.in");
        ofstream fout("bfs.out");
        int n,m,nc;
        fin>>n>>m>>nc;

        vector<int> adj[n+5] = {};
        vector<int> viz(n+5, 0);
        vector<int> ans(n+5, 0);
        queue<pair<int,int>> q ={};
       // for(auto it:viz)
       //     cout<<it<<" ";
       // cout<<'\n';

        for(int i=1;i<=m;i++)
        {
            int x,y;
            fin>>x>>y;
            if(x!=y)
                adj[x].push_back(y);
        }
        /*
        for(int i=1;i<=n;i++)
        {
            cout<<i<<" : ";
            for(auto it:adj[i])
                cout<<it<<" ";
            cout<<'\n';
        }
        cout<<"---------------\n";
        */
        q.push(make_pair(nc,0));
        viz[nc] = 1;

        Graf G (n,m);
        G.bfs(fin,fout,q,adj,viz,ans,nc);
    }
    if(problema == 1)
    {
        ifstream fin("dfs.in");
        ofstream fout("dfs.out");
        int n,m;
        fin>>n>>m;
        vector<int> adj[n+5] = {};
        vector<int> viz(n+5,0);
        for(auto it:viz)
            cout<<it<<" ";
        cout<<'\n';
        for(int i=1;i<=m;i++)
        {
            int x,y;
            fin>>x>>y;
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        for(int i=1;i<=n;i++)
            if(adj[i].size())
                {
                    cout<<i<<" : ";
                    for(auto it : adj[i])
                        cout<<it<<" ";
                    cout<<'\n';
                }
        cout<<"-----------------\n\n";

        Graf G (n,m);
        fout<<G.nr_connected_components(adj,viz);
    }

    return 0;
}