TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2128
  • Problem
  • P2128简单图论问题
    Limits : Time Limit : 10000 MS   Memory Limit : 524288 KB
    Judgment Tips : 2s,512MB
    Description

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

    Input Format

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

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

    Output Format

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

    Sample Input

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

    Sample Output

    No
    No
    No
    No
    No
    Yes

    Hint

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

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