最大可能身高问题

题目描述

有 $N$ 头牛站成一行，被编队为 $1, 2, 3, \dots, N$，每头牛的身高都为整数。

当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。

现在，我们只知道其中最高的牛是第 $P$ 头，它的身高是 $H$，剩余牛的身高未知。

但是，我们还知道这群牛之中存在着 $M$ 对关系，每对关系都指明了某两头牛 $A$ 和 $B$ 可以相互看见。

求每头牛的身高的最大可能值是多少。

输入格式

第一行输入整数 $N, P, H, M$，数据用空格隔开。

接下来 $M$ 行，每行输出两个整数 $A$ 和 $B$，代表牛 $A$ 和牛 $B$ 可以相互看见，数据用空格隔开。

输出格式

一共输出 $N$ 行数据，每行输出一个整数。

第 $i$ 行输出的整数代表第 $i$ 头牛可能的最大身高。

输入输出样例 #1

输入 #1

9 3 5 5
1 3
5 3
4 3
3 7
9 8

输出 #1

5
4
5
3
4
4
5
5
5

输入输出样例 #2

输入 #2

5 2 10 2
1 4
3 5

输出 #2

10
10
9
9
8

限制条件

• $1 \le N \le 5000$
• $1 \le H \le 1000000$
• $1 \le A, B \le 10000$
• $A \neq B$
• $0 \le M \le 10000$

注意

1. 此题中给出的关系对可能存在重复。
2. 关系对 $A$ 和 $B$ 中，较小的编号在前，较大的编号在后（即 $A < B$）。
3. 当两头牛 $A$ 和 $B$ 可以相互看见时，意味着它们之间的所有牛身高都严格小于它们的身高。

样例解释 #1

有 $9$ 头牛，第 $3$ 头牛最高，身高为 $5$。

已知关系：

• 牛 $1$ 和牛 $3$ 可以相互看见
• 牛 $3$ 和牛 $5$ 可以相互看见
• 牛 $3$ 和牛 $4$ 可以相互看见
• 牛 $3$ 和牛 $7$ 可以相互看见
• 牛 $8$ 和牛 $9$ 可以相互看见

为了最大化每头牛的身高，同时满足这些相互看见的关系，得到如上输出结果。