P2879 [USACO07JAN] Tallest Cow S

FarmerJohn 有n头牛，它们按顺序排成一列。FarmerJohn 只知道其中最高的奶牛的序号及它的高度，其他奶牛的高度都是未知的。现在 FarmerJohn 手上有 $R$ 条信息，每条信息上有两头奶牛的序号（$a$ 和 $b$），其中 $b$ 奶牛的高度一定大于等于 $a$ 奶牛的高度，且 $a, b$之间的所有奶牛的高度都比 $a$ 小。现在 FarmerJohn 想让你根据这些信息求出每一头奶牛的可能的最大的高度。（数据保证有解）

无

无

$1 \le n \le 10000$，$1 \le h \le 1000000$，$0 \le R \le 10000$ Translate provided by @酥皮