#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
int main() {
    ll n,m;
    cin>>n>>m;
    vector<ll> g[n+1];
    ll i=1;
    for(int i=1;i<=m;i++){
    	ll u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
 
    queue<ll> q;
    ll src;
    cin>>src;
    q.push(src);
    ll vi[n+1]={0};
    vi[src]=1;
    ll lvl[n+1]={0};
    lvl[src]=0;
    while(!q.empty()) {
        ll v=q.front();
        q.pop();
        for(auto u:g[v]) {
            if(vi[u]==0) {
                q.push(u);
                vi[u]=1;
                lvl[u]=lvl[v]+1;
            }
        }
    }
    i=1;
 
    while(i<=n) {
        if(vi[i]==0) {
            cout<<"not";
        } else {
            cout<<i; 
        }
        cout<<'\n';
        i++;
    }
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGludCBsbDsKCmludCBtYWluKCkgewogICAgbGwgbixtOwogICAgY2luPj5uPj5tOwogICAgdmVjdG9yPGxsPiBnW24rMV07CiAgICBsbCBpPTE7CiAgICBmb3IoaW50IGk9MTtpPD1tO2krKyl7CiAgICAJbGwgdSx2OwogICAgICAgIGNpbj4+dT4+djsKICAgICAgICBnW3VdLnB1c2hfYmFjayh2KTsKICAgICAgICBnW3ZdLnB1c2hfYmFjayh1KTsKICAgIH0KICAgIAogICAgcXVldWU8bGw+IHE7CiAgICBsbCBzcmM7CiAgICBjaW4+PnNyYzsKICAgIHEucHVzaChzcmMpOwogICAgbGwgdmlbbisxXT17MH07CiAgICB2aVtzcmNdPTE7CiAgICBsbCBsdmxbbisxXT17MH07CiAgICBsdmxbc3JjXT0wOwogICAgd2hpbGUoIXEuZW1wdHkoKSkgewogICAgICAgIGxsIHY9cS5mcm9udCgpOwogICAgICAgIHEucG9wKCk7CiAgICAgICAgZm9yKGF1dG8gdTpnW3ZdKSB7CiAgICAgICAgICAgIGlmKHZpW3VdPT0wKSB7CiAgICAgICAgICAgICAgICBxLnB1c2godSk7CiAgICAgICAgICAgICAgICB2aVt1XT0xOwogICAgICAgICAgICAgICAgbHZsW3VdPWx2bFt2XSsxOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgaT0xOwogICAgCiAgICB3aGlsZShpPD1uKSB7CiAgICAgICAgaWYodmlbaV09PTApIHsKICAgICAgICAgICAgY291dDw8Im5vdCI7CiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgY291dDw8aTsgCiAgICAgICAgfQogICAgICAgIGNvdXQ8PCdcbic7CiAgICAgICAgaSsrOwogICAgfQogICAgcmV0dXJuIDA7Cn0=

NSA0CjEgMgoxIDMKMyA0CjMgNQoxCg==

5 4
1 2
1 3
3 4
3 5
1