#P3073. [Pa2011]Journeys

    ID: 2206 传统题 8000ms 512MiB 尝试: 915 已通过: 173 难度: 7 上传者: 标签>CF2200提高+/省选-广度优先搜索普通线段树线段树上二分有序集合优化建图

[Pa2011]Journeys

题目描述

一个星球上有 nn 个国家和许多双向道路,国家用 1∼n1\sim n 编号。

但是道路实在太多了,不能用通常的方法表示。于是我们以如下方式表示道路:(a,b),(c,d)(a,b),(c,d) 表示,对于任意两个国家 x,yx,y,如果 a≤x≤b,c≤y≤da\le x\le b,c\le y\le d,那么在 x,yx,y 之间有一条道路。

首都位于 PP 号国家。你想知道 PP 号国家到任意一个国家最少需要经过几条道路。保证 PP 号国家能到任意一个国家。

输入格式

第一行三个整数 n,m,Pn,m,P。

之后 mm 行,每行 44 个整数 a,b,c,da,b,c,d。

输出格式

nn 行,第 ii 行表示 PP 号国家到第 ii 个国家最少需要经过几条路。

样例 #1

样例输入 #1

5 3 4
1 2 4 5
5 5 4 4
1 1 3 3

样例输出 #1

1
1
2
0
1

提示

对于所有测试点,保证 1≤n≤5×1051\le n\le 5\times 10^5,1≤m≤1051\le m\le 10^5,1≤a≤b≤n1\le a\le b\le n,1≤c≤d≤n1\le c\le d\le n。