TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1599
  • Problem
  • P1599【Usaco Jan07 Silver】最大身高
    Limits : Time Limit : 10000 MS   Memory Limit : 265536 KB
    Description

    FJ的N(1 <= N <= 5,000)头奶牛站成一排,并从左到右被编号为1..N。每头奶牛都有一个正整数的身高,具体的值FJ暂时保密,但会告诉你它们当中最高的一头的编号I和身高H(1 <= H <= 1,000,000)的值。

    FJ制作一张包含R(0 <= R <= 10,000)行的列表,每行的都是形如“第17号奶牛能看到第34号奶牛”,其意义是34号奶牛的身高不低于17号奶牛的身高,并且在17号和34号之间的奶牛的身高都严格低于17号奶牛的身高。

    请你确定奶牛每头奶牛的最大可能的身高,我们保证给出的数据都是正确的,并且一定有满足限制条件的解。

    Input Format

    第1行:包含四个用空格分开的整数:N, I, H 和 R
    第2..R+1行:每行包含两个用空格分开的整数A和B(1 <= A,B <= N),表示奶牛A能看到奶牛B

    Output Format

    第1..N行:第i行包含一个整数,表示第i头奶牛的最大身高。

    Sample Input

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

    Sample Output

    5
    4
    5
    3
    4
    4
    5
    5
    5


    Source  Usaco Jan07 Silver