거미줄 걷기

샬롯은 거미로, 자기 거미줄의 중심에 앉아 있다. 거미줄은 중심에서 바깥 경계까지 이어지는 직선 실 여러 가닥으로 이루어진다. 거미줄에는 다리도 있는데, 각 다리는 인접한 두 실을 잇는다. 다리의 두 끝점은 중심에서 항상 같은 거리에 있다.

샬롯은 밤늦게 중심에서 식사를 마치고 구석으로 물러나고 싶을 때, 자동 조종 방식으로 가장자리까지 걷는다. 시작할 실을 고른 뒤, 그 실에서 처음 만나는 다리까지 걷는다. 다리를 건너 다른 실로 넘어간 다음, 바깥쪽으로 계속 걸어 다음 다리를 만난다. 샬롯은 그 다리도 건너고, 이 과정을 반복한다. 현재 실에 다리가 더 이상 없으면 그 실의 끝까지 걷는다. 샬롯은 만나는 다리를 모두 반드시 건너야 한다. 그림은 샬롯이 택할 수 있는 한 경로를 보여 준다.

그림 I.1: 실 4에서 시작하는 경로.

샬롯이 낮에 자러 가는 가장 좋아하는 구석은 실 $s$의 끝이다. 시작할 수 있는 실마다, 샬롯이 $s$에서 끝나도록 원래 거미줄에 추가해야 하는 다리의 최소 개수를 구한다. 샬롯은 실의 어느 지점에나 다리를 추가할 수 있지만, 추가한 다리가 다른 다리와 닿아서는 안 된다. 추가하는 다리의 두 끝점은 중심에서 같은 거리에 있어야 하며, 다리는 인접한 두 실을 이어야 한다.

첫 줄에 세 정수 $n$, $m$, $s$가 주어진다. $3 \le n \le 200000$은 실의 개수, $0 \le m \le 500000$은 다리의 개수, $1 \le s \le n$은 샬롯이 좋아하는 실이다. 실은 반시계 방향으로 1부터 $n$까지 번호가 매겨져 있다. 나머지 $m$개 줄에는 다리를 나타내는 두 정수 $d$와 $t$가 주어진다. $1 \le d \le 10^9$은 다리의 중심으로부터의 거리이고, $1 \le t \le n$은 반시계 방향으로 보았을 때 다리의 첫 번째 실이다. $1 \le t < n$이면 다리는 실 $t$와 $t+1$을 잇는다. $t = n$이면 다리는 실 $1$과 $n$을 잇는다. 모든 다리의 거리 $d$는 서로 다르다.

$n$개의 줄을 출력한다. $i$번째 줄에는 실 $i$에서 자동 조종으로 걷기 시작했을 때, 샬롯이 실 $s$에서 끝나기 위해 추가해야 하는 다리의 최소 개수를 출력한다.