여정

시간 제한1초메모리 제한128 MB

요약

서로 겹치지 않는 두 구간의 모든 마을을 잇는 m개의 도로 묶음이 주어질 때, p번 마을에서 모든 마을까지 도로 개수 기준 최단 거리를 구한다.

난이도: 어려움10점 중 9점
유형: 그래프, BFS, 세그먼트 트리, 그리디
정답자: 아직 제출이 없습니다

문제

바이트국(Byteotia)에는 $1$ 번부터 $n$ 번까지 번호가 매겨진 도시 $n$ 개가 있다. 고속도로는 자주 놓이지 않지만, 한 번 놓일 때는 큰 묶음 단위로 건설된다. 지금까지 모두 $m$ 개의 묶음이 건설되었으며, $i$ 번째 묶음은 번호가 $[a_i, b_i]$ 에 속하는 도시와 번호가 $[c_i, d_i]$ 에 속하는 도시를 잇는 모든 고속도로로 이루어진다. 고속도로는 도시에서만 서로 만나며, 터널이나 고가도로를 통해 서로를 지나칠 수 있다. 이 고속도로망을 이용하면 임의의 두 도시 사이를 오갈 수 있다. 고속도로 하나를 타는 데는 정확히 $1$ 달러가 든다.

바이트아사르(Byteasar)는 고향으로 돌아와 수도인 비트시티(Bitcity), 곧 $p$ 번 도시에 정착하려 한다. 여러 도시에 흩어져 사는 옛 친구들을 모두 방문하고 싶은 그는, 고속도로망만 이용해 비트시티에서 다른 모든 도시로 가는 최소 비용을 알고 싶어 한다. 이 값을 구하여라.

입력

첫째 줄에 세 정수 $n$ , $m$ , $p$ 가 주어진다 ( $2 \le n \le 500000$ , $1 \le m \le 100000$ , $1 \le p \le n$ ). 각각 도시의 수, 고속도로 묶음의 수, 그리고 바이트아사르가 사는 도시(비트시티)의 번호이다.

이어지는 $m$ 개의 줄에는 각 묶음의 정보가 한 줄에 하나씩, 네 정수 $a_i$ , $b_i$ , $c_i$ , $d_i$ 로 주어진다 ( $1 \le a_i \le b_i \le n$ , $1 \le c_i \le d_i \le n$ , $[a_i, b_i] \cap [c_i, d_i] = \varnothing$ ). 이는 $[a_i, b_i]$ 에 속하는 모든 도시가 $[c_i, d_i]$ 에 속하는 모든 도시와 양방향 고속도로로 연결됨을 뜻한다. 각 고속도로는 많아야 한 묶음에만 속한다.

출력

$n$ 개의 줄을 출력한다. $i$ 번째 줄에는 비트시티에서 $i$ 번 도시까지 가는 최소 비용(달러)을 출력한다. 따라서 $p$ 번째 줄의 값은 $0$ 이다.

힌트

예제6

예제 1

입력

예상 출력

예제 2
입력
```
2 1 1
1 1 2 2
```
예상 출력
```
0
1
```
예제 3
입력
```
2 1 2
1 1 2 2
```
예상 출력
```
1
0
```
예제 4
입력
```
4 3 1
1 1 2 2
2 2 3 3
3 3 4 4
```
예상 출력
```
0
1
2
3
```
예제 5
입력
```
6 1 1
1 3 4 6
```
예상 출력
```
0
2
2
1
1
1
```

예제 6

입력

예상 출력