TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P2128
  • 問題
  • P2128简单图论问题
    制限 : 時間制限 : 10000 MS   メモリ制限 : 524288 KB
    審判説明 : 2s,512MB
    問題説明

    给定一个 \(n\) 个节点 \(m\) 条边的简单有向无环图,对于一条边 \(u\to v\) ,判断 \(u,v\) 之间是否存在一条不经过这条边的路径。

    入力形式

    第一行两个整数 \(n,m\) ,即节点数和边数。

    接下来 \(m\) 行,每行两个整数 \(u,v\) ,表示一条有向边 \(u\to v\)

    出力形式

    输出 \(m\) 行,表示每条边的判断结果,路径存在输出 Yes ,不存在输出 No

    サンプル入力

    5 6
    1 2
    1 3
    2 4
    3 5
    2 5
    1 5

    サンプル出力

    No
    No
    No
    No
    No
    Yes

    ヒント

    对于0%的数据, \(n\leq 1000\)\(m\leq 3000\)

    对于100%的数据, \(n\leq 100000\)\(m\leq 300000\)