题目描述

FJ 的 N（1 ≤ N ≤ 10,000）头奶牛站成一列，编号为 1 到 N。每头奶牛的身高是一个正整数（这是一个小秘密）。你只知道最高的奶牛的身高 H（1 ≤ H ≤ 1,000,000）以及它的编号 I。

FJ 记录了 R（0 ≤ R ≤ 10,000）条信息，格式为“奶牛 17 能看到奶牛 34”。这表示：

• 奶牛 34 的身高至少和奶牛 17 一样高；
• 并且在 17 和 34 之间的所有奶牛的身高严格小于奶牛 17 的身高。

请计算每头奶牛可能的最大身高，使得所有已知信息都成立。题目保证存在可行解。

输入格式

第 1 行：4 个空格分隔的整数 N、I、H、R。
第 2 到 R+1 行：每行两个不同的整数 A 和 B（1 ≤ A, B ≤ N），表示奶牛 A 能看到奶牛 B。

输出格式

第 1 到 N 行：第 i 行表示奶牛 i 的最大可能身高。

输入样例 1

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

输出样例 1

5  
4  
5  
3  
4  
4  
5  
5  
5  

题目来源

USACO 2007 年 1 月银级

关键说明

• 对于每对 (A, B)，假设 A < B，则 A 到 B 之间的奶牛（即 A+1 到 B-1）的身高必须严格小于 A 和 B 的身高；
• 最高的奶牛编号为 I，身高为 H，且可能有多头奶牛达到最高身高（如样例中编号 3 和 7 的奶牛）。