#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int,int> tp;
const int N = 1e6 + 5;
const int oo = 2e9;

int n, m, s;
vector<pii> vr[N];
vector<int> f[5][N], p[N];
deque<tp> pq;

void update(int t,int u,int v,int w,int type){
  if(f[t][u][v] <= w) return;
  if(!type) pq.push_front({f[t][u][v] = w, t, u, v});
  else pq.push_back({f[t][u][v] = w, t, u, v});
}

void pro(int w,int u,int v){
  int bf = (u == 1 ? n : u - 1), nx = (u == n ? 1 : u + 1);
  int nb = lower_bound(all(p[bf]), v) - p[bf].begin(),
   nt = lower_bound(all(p[nx]), v) - p[nx].begin();
  bool f1 = true, f2 = true;
  if(nb < p[bf].size() && p[bf][nb] == v && vr[bf][nb].se != 2) f1 = false;
  if(nt < p[nx].size() && p[nx][nt] == v && vr[nx][nt].se != 2) f2 = false;
  if(f1){
    nb--;
    if(p[bf][nb] == v - 1) update(1, bf, nb, w + 1, 1);
    else update(0, bf, nb, w + 1, 1);
  }
  if(f2){
    nt--;
    if(p[nx][nt] == v - 1) update(1, nx, nt, w + 1, 1);
    else update(0, nx, nt, w + 1, 1);
  }
}

set<int> g[N], h[N];

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }
  cin >> n >> m >> s;
  for(int i = 1; i <= m; i ++){
    int d, t; cin >> d >> t;
    int nxt = (t == n ? 1 : t + 1);
    vr[nxt].pb({d, 0});
    vr[t].pb({d, 1});
    p[nxt].pb(d);
    p[t].pb(d);
  }
  for(int i = 1; i <= n; i ++){
    p[i].pb(0);
    vr[i].pb({0, 2});
  }
  for(int i = 1; i <= n; i ++){
    int bf = (i == 1 ? n : i - 1), nt = (i == n ? 1 : i + 1);
    for(auto j : p[bf]) g[i].insert(j);
    for(auto j : p[nt]) g[i].insert(j);
    for(auto j : p[i]) h[i].insert(j);
  }
  for(int i = 1; i <= n; i ++){
    for(auto j : g[i]) if(h[i].find(j) == h[i].end())
      p[i].pb(j), vr[i].pb({j, 2});

    sort(all(p[i]));
//    cerr << i << " k\n";
//    for(auto j : p[i]) cerr << j << " ";
//    cerr << "\n";
    sort(all(vr[i]));
    for(auto j : p[i]){
      f[0][i].pb(oo);
      f[1][i].pb(oo);
    }
  }

  int ans = oo;
  pq.push_front({f[0][s][vr[s].size() - 1] = 0, 0, s, vr[s].size() - 1});
  while(!pq.empty()){
    int w, t, u, v; tie(w, t, u, v) = pq.front(); pq.pop_front();
//    cerr << w << " " << t << " " << u << " " << v << " g\n";
    if(w > f[t][u][v]) continue;
    if(!v){
      continue;
    }

    if(t == 1){
      if(vr[u][v].se == 2){
        pro(w, u, vr[u][v].fi);
        update(0, u, v - 1, w, 0);
        continue;
      }
      int nt = (vr[u][v].se ? u + 1 : u - 1);
      if(!nt) nt = n; if(nt > n) nt = 1;
      int k = lower_bound(all(p[nt]), p[u][v]) - p[nt].begin();
      if(k == 1) update(0, nt, 0, w, 0);
      else{
        if(p[nt][k - 1] == p[nt][k] - 1) update(1, nt, k - 1, w, 0);
        else update(0, nt, k - 1, w, 0);
      }
    }else{
      pro(w, u, vr[u][v].fi + 1);
      update(1, u, v, w, 0);
    }
  }
  for(int i = 1; i <= n; i ++) cout << min(f[1][i][0], f[0][i][0]) << "\n";
}