#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
const int N=2e5+10,M=5e5+10,V=N+M*2,INF=1e9;
int n,m,k,s,d[M],t[M],dis[V];
vector<int>p[N],id[N];
vector<pair<int,int> >to[V];
void add(int u,int v,int w){
	// if(!w)debug(u,v,w);
	to[u].push_back({v,w});
}
#define v e.first
#define w e.second
void dij(int s,int *d){
	deque<int>q;
	fill(d+1,d+1+k,INF),q.push_back(s),d[s]=0;
	for(int u;!q.empty();){
		u=q.front(),q.pop_front();
		for(auto e:to[u]){
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				if(w)q.push_back(v);
				else q.push_front(v);
			}
		}
	}
}
#undef v
#undef w
int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&d[i],&t[i]);
		p[t[i]].push_back(d[i]);
		p[t[i]%n+1].push_back(d[i]);
	}
	for(int i=1;i<=n;i++){
		sort(p[i].begin(),p[i].end());
		p[i].push_back(INF);
		id[i].assign(p[i].size(),0);
		iota(id[i].begin(),id[i].end(),k+1);
		k+=id[i].size();
	}
	// debug(s);
	s=id[s].back();
	for(int i=1;i<=m;i++){
		int u=t[i],v=t[i]%n+1;
		// debug(p[u],p[v],d[i]);
		int x=lower_bound(p[u].begin(),p[u].end(),d[i])-p[u].begin();
		int y=lower_bound(p[v].begin(),p[v].end(),d[i])-p[v].begin();
		add(id[u][x+1],id[v][y],0),add(id[v][y+1],id[u][x],0);
	}
	// debug(id[3],p[3]);
	// debug(id[4],p[4]);
	// debug(id[5],p[5]);
	// debug(id[6],p[6]);
	for(int u=1;u<=n;u++){
		int v=u%n+1;
		int l1=p[u].size(),l2=p[v].size();
		for(int i=0,j=0;i<l1&&j<l2;){
			if(p[u][i]>=p[v][j])add(id[u][i],id[v][j],1);
			if(p[v][j]>=p[u][i])add(id[v][j],id[u][i],1);
			if(p[u][i]<p[v][j])i++;
			else j++;
		}
	}
	dij(s,dis);
	for(int i=1;i<=n;i++)printf("%d\n",dis[id[i][0]]);
	return 0;
}