#13. 最高的牛

最高的牛

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

N\red{N} 头牛站成一行,被编队为123N\red{1、2、3…N},每头牛的身高都为整数。

当且仅当两头牛中间的牛身高都比它们矮时,两头牛方可看到对方。

现在,我们只知道其中最高的牛是第 P\red{P} 头,它的身高是 H\red{H} ,剩余牛的身高未知。

但是,我们还知道这群牛之中存在着 M\red{M} 对关系,每对关系都指明了某两头牛 A\red{A}B\red{B} 可以相互看见。

求每头牛的身高的最大可能值是多少。

输入格式

第一行输入整数N,P,H,M\red{N,P,H,M},数据用空格隔开。

接下来M\red{M}行,每行输出两个整数 A\red{A}B\red{B} ,代表牛 A\red{A} 和牛 B\red{B} 可以相互看见,数据用空格隔开。

输出格式

一共输出 N\red{N} 行数据,每行输出一个整数。

i\red{i} 行输出的整数代表第 i\red{i} 头牛可能的最大身高。

样例

输入数据

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

输出数据

5
4
5
3
4
4
5
5
5

提示

1N10000\red{1≤N≤10000},

1H1000000\red{1≤H≤1000000},

1A,B10000\red{1≤A,B≤10000},

0M10000\red{0≤M≤10000}

国庆j组4

未参加
状态
已结束
规则
OI
题目
4
开始于
2021-10-4 17:00
结束于
2021-10-4 23:00
持续时间
6 小时
主持人
参赛人数
6