P2879 [USACO07JAN] Tallest Cow S

题目描述

FJ 的 $N$ 头奶牛($1 \le N \le 10,000$)按编号 $1$ 到 $N$ 排成一行。每头奶牛有一个正整数表示的身高(这是个秘密)。现在你只知道最高奶牛的身高 $H$($1 \le H \le 1,000,000$),以及它的编号 $I$。 FJ 提供了 $R$ 条信息($0 \le R \le 10,000$),每条信息形如“奶牛 17 能看到奶牛 34”。这意味着奶牛 34 的身高不小于奶牛 17 的身高,并且编号在 17 和 34 之间的所有奶牛,其身高都严格小于奶牛 17 的身高。 现在请你计算出对于每一头奶牛(编号从 $1$ 到 $N$),在所有给定信息都成立的前提下,它可能具有的最大身高。 题目保证一定存在满足条件的解。

输入格式

输出格式