181. [USACO Jan07]Tallest Cow 最高的牛

【题目描述】

为了方便我们把 $FJ$ 养的$N$头$(1 ≤ N ≤ 10,000)$奶牛从$1$号开始编号，一直编到$N$号，并且让他们站成一列。每头牛都有一个正整数用来描述她的身高(有些牛不愿意说，她们的身高保密)。你只知道这些牛中最高的那一头的身高是$H$，她的编号是第$i$号。

$FJ$写了一张单子，上面有$R$个陈述句，大概是”第$17$号牛可以看见第$34$号牛”这种。这意味着第$34$号牛最起码和第$17$号牛一样高。而且$17$号牛和$34$号牛之间的牛得身高都严格的小于$min(h[17],h[34])$。

从第$1$号牛到第$N$号牛，求她们可能拥有的最大身高，所给出的所有信息都是正确的。这可以保证满足所有条件。

【输入格式】

第$1$行：四个由空格分开的整数，$N，i，H和R$。

第$2..R+1$行：两个由空格分开的整数$A$和$B(1 ≤ A, B ≤ N)$,表示第$A$号牛可以看到第$B$号牛。

【输出格式】

第$1..N$行:第$i$行包括第$i$号牛可能拥有的最大身高。

【输入样例】

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

【输出样例】

5
4
5
3
4
4
5
5
5

【输入解释】

由$9$头奶牛，第三头奶牛最高，身高是$5$.

【题目翻译】

译$by$ $KZFFFFFFFF$