时间限制：1000 ms
内存限制：125 MiB
标准输入输出
题目类型：传统
评测方式：文本比较
FJ 的 头奶牛（）按编号 到 排成一行。每头奶牛有一个正整数表示的身高（这是个秘密）。现在你只知道最高奶牛的身高 （），以及它的编号 。
FJ 提供了 条信息（），每条信息形如“奶牛 17 能看到奶牛 34”。这意味着奶牛 34 的身高不小于奶牛 17 的身高，并且编号在 17 和 34 之间的所有奶牛，其身高都严格小于奶牛 17 的身高。
现在请你计算出对于每一头奶牛（编号从 到 ），在所有给定信息都成立的前提下，它可能具有的最大身高。
题目保证一定存在满足条件的解。
第 行：四个用空格分隔的整数：，， 和 。
第 到第 行：每行两个不同的整数 和 （, ），表示奶牛 能看到奶牛 。
样例输入
9 3 5 5
1 3
5 3
4 3
3 7
9 8
样例输出