#1635. [Usaco2007 Jan]Tallest Cow 最高的牛

[Usaco2007 Jan]Tallest Cow 最高的牛

题目描述

NN 头牛站成一行。两头牛能够相互看见,当且仅当他们中的牛逗比他们矮。现在我们只知道最高的牛是第 PP 头,身高为 HH,不知道剩余 N1N-1 头牛的身高。但是,没我们还知道 MM 对关系,每对关系包含了两个整数 A,BA,B,表示编号为 AA 的牛和编号为 BB 的牛可以互相看见,求每头牛的身高最大可能是多少。

输入格式

第一行包含四个正整数 N,P,H,MN,P,H,M,如题意所示。

接下来 MM 行每行两个正整数 A,BA,B,表示编号为 AA 的牛和编号为 BB 的牛可以互相看见。

输出格式

输出 NN 行,每行 11 个整数,表示第 ii 头牛最高可能的身高。

9 3 5 5
1 3
5 3
4 3
3 7
9 8
INPUT DETAILS:
There are 9 cows, and the 3rd is the tallest with height 5.

5
4
5
3
4
4
5
5
5

提示

1N,M1041\leq N,M\leq 10^4,1P1041\leq P\leq 10^4,1H1061\leq H\leq 10^6