题目描述

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

输入格式

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

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

输出格式

输出 $N$ 行，每行 $1$ 个整数，表示第 $i$ 头牛最高可能的身高。

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

提示

$1\leq N,M\leq 10^4$,$1\leq P\leq 10^4$,$1\leq H\leq 10^6$