Tallest Cow

题目描述

FJ的N（1≤N≤10000）头奶牛方便地索引1..N排成一行。每头牛都有一个正整数的高度（这有点秘密）。你只会被告知最高奶牛的身高H（1≤H≤1000000）以及该奶牛的指数I。 FJ列出了“17头牛看到34头牛”形式的R（0≤R≤10000）行。这意味着奶牛34至少和奶牛17一样高，并且17至34之间的每头牛的高度都严格小于奶牛17的高度。 对于从1..N开始的每头牛，确定其可能的最大高度，以便所有给出的信息仍然正确。保证有可能满足所有的约束条件。

输入格式

第1行：四个空格分隔的整数：N、I、H和R

第2行…R+1：两个不同的空间分隔整数A和B（1≤A，B≤N），表明牛A可以看到牛B。

输出格式

Lines 1…N: Line i contains the maximum possible height of cow i.

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

5
4
5
3
4
4
5
5
5

提示

（暂无提示）

来源

童程童美