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

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGludCBsbDsKCmludCBtYWluKCkgewogICAgbGwgbjsKICAgIGNpbj4+bjsKICAgIGxsIG07CiAgICBjaW4+Pm07CiAgICB2ZWN0b3I8bGw+IGdbbis1XTsKICAgIGxsIGk9MTsKICAgIHdoaWxlKGk8PW0pIHsKICAgICAgICBsbCB1LHY7CiAgICAgICAgY2luPj51Pj52OwogICAgICAgIGdbdV0ucHVzaF9iYWNrKHYpOwogICAgICAgIGdbdl0ucHVzaF9iYWNrKHUpOwogICAgICAgIGkrKzsKICAgIH0KICAgIHF1ZXVlPGxsPiBxOwogICAgbGwgc3JjOwogICAgY2luPj5zcmM7CiAgICBxLnB1c2goc3JjKTsKICAgIGxsIHVzW24rNV09ezB9OwogICAgdXNbc3JjXT0xOwogICAgbGwgbHZsW24rNV09ezB9OwogICAgbHZsW3NyY109MDsKICAgIHdoaWxlKCFxLmVtcHR5KCkpIHsKICAgICAgICBsbCB2PXEuZnJvbnQoKTsKICAgICAgICBxLnBvcCgpOwogICAgICAgIGZvcihhdXRvIHU6Z1t2XSkgewogICAgICAgICAgICBpZih1c1t1XT09MCkgewogICAgICAgICAgICAgICAgcS5wdXNoKHUpOwogICAgICAgICAgICAgICAgdXNbdV09MTsKICAgICAgICAgICAgICAgIGx2bFt1XT1sdmxbdl0rMTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIGk9MTsKICAgIHdoaWxlKGk8PW4pIHsKICAgICAgICBjb3V0PDxsdmxbaV08PCIgIjsKICAgICAgICBpKys7CiAgICB9CiAgICByZXR1cm4gMDsKfQo=

NSA0CjEgMgoxIDMKMyA0CjMgNQoxCg==

5 4
1 2
1 3
3 4
3 5
1