7073: BZOJ3073：[Pa2011]Journeys

Memory Limit：512 MB Time Limit：1 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Seter建造了一个很大的星球，他准备建造N个国家和无数双向道路。N个国家很快建造好了，用1..N编号，但是他发现道路实在太多了，他要一条条建简直是不可能的！于是他以如下方式建造道路：(a,b),(c,d)表示，对于任意两个国家x,y，如果a<=x<=b,c<=y<=d，那么在xy之间建造一条道路。Seter保证一条道路不会修建两次，也保证不会有一个国家与自己之间有道路。 Seter好不容易建好了所有道路，他现在在位于P号的首都。Seter想知道P号国家到任意一个国家最少需要经过几条道路。当然，Seter保证P号国家能到任意一个国家。 



注意：可能有重边 
输入格式



第一行三个数N,M,P。N<=500000,M<=100000。
后M行，每行4个数A，B，C，D。1<=A<=B<=N,1<=C<=D<=N。









输出格式



N行，第i行表示P号国家到第i个国家最少需要经过几条路。显然第P行应该是0。










样例输入
5 3 4
1 2 4 5
5 5 4 4
1 1 3 3



样例输出
1
1
2
0
1
提示
没有写明提示
题目来源
seter翻译
	  

    

  

    
              

  
    

      

        

        加入题单
        

        


		

		
		上一题  下一题		算法标签：