TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  課程の中心  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P1599
  • 問題
  • P1599【Usaco Jan07 Silver】最大身高
    制限 : 時間制限 : 10000 MS   メモリ制限 : 265536 KB
    問題説明

    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号奶牛的身高。

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

    入力形式

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

    出力形式

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

    サンプル入力

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

    サンプル出力

    5
    4
    5
    3
    4
    4
    5
    5
    5


    ソース  Usaco Jan07 Silver