comp

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

#define pb push_back
#define mp make_pair
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

using namespace std;
const int maxn = int(1e5) + 10;

int used[maxn], p[maxn][30], used_up[maxn], d[maxn], us[maxn], even[maxn], ret[maxn];
vector <int> a[maxn], a1[maxn], q, g[maxn];
map < pair <int, int>, int> ma;

void dfs_up ( int v)
{
    used_up[v] = 1;
    for ( int i = 0; i < (int)g[v].size(); i++) {
        int to = g[v][i];
        d[to] = d[v] + 1;
        if (used_up[to] == 0) {
            dfs_up(to);
            p[to][0] = v;
        }
    }
}
int col, tim;
void paint (int v)
{
        eprintf("paint %d!\n", v);
        for (int i = 0; i < (int)q.size(); i++) eprintf("%d%c", q[i], " \n"[i + 1 == (int)q.size()]);
    col++;
    while (!q.empty()){
                int u = q.back();
        used[u] = col;
        q.pop_back();
                if (u == v) break;
    }
}


void dfs (int v, int p = -1)
{
    tim++;
    us[v] = 1;
    q.pb(v);
    even[v] = tim;
    ret[v] = tim;
    for (auto to : a[v]){
        if (to == p) {
                    continue;
                }
        if ( us[to] == 1){
            ret[v] = min(ret[v], even[to]);
                } else {
            dfs(to, v);
            ret[v] = min(ret[v], ret[to]);
            if (ret[to] > even[v]) {
                paint(to);
                            }
        }
    }
}


int main()
{
    int n, m;
    scanf("%d%d",&n, &m);
        int f;
        scanf("%d", &f);
        f--;

        for (int i = 0; i < n; i++) used[i] = -1;
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        u--, v--;
        a[u].pb(v);
        a[v].pb(u);
    }
    dfs(f);
    paint(f);

    for ( int i = 0; i < n; i++)
        printf("%d ", used[i]);
    printf("\n");
}