TouchStone
  Please Login
ログイン 登録
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P6413
  • 問題
  • P6413[CSP-J 2019]加工零件
    制限 : 時間制限 : 20000 MS   メモリ制限 : 262144 KB
    審判説明 : 1s,256MB
    問題説明

    凯凯的工厂正在有条不紊地生产一种神奇的零件,神奇的零件的生产过程自然也很神奇。工厂里有$n$位工人,工人们从$1\sim n$编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带。

    如果$x$号工人想生产一个被加工到第$L(L>1)$阶段的零件,则所有与$x$号工人有传送带直接相连的工人,都需要生产一个被加工到第$L-1$阶段的零件(但$x$号工人自己无需生产第$L−1$阶段的零件。

    如果$x$号工人想生产一个被加工到第$1$阶段的零件,则所有与$x$号工人有传送带直接相连的工人,都需要为$x$号工人提供一个原材料。

    轩轩是$1$号工人。现在给出$q$张工单,第$i$张工单表示编号为$a_i$的工人想生产一个第$L_i$阶段的零件。轩轩想知道对于每张工单,他是否需要给别人提供原材料。他知道聪明的你一定可以帮他计算出来!

    入力形式

    第一行两个正整数$n,m,q$,分别表示工人的数目、传送带的数目和工单的数目。

    接下来$m$行,每行两个正整数$u$和$v$,表示编号为$u$和$v$的工人之间存在一条零件传输带。保证$u\neq v$。

    接下来$q$行,每行两个正整数$a$和$L$,表示编号为$a$的工人想生产一个第$L$阶段的零件。

    出力形式

    共$q$行,每行一个字符串“Yes”或者“No”。如果按照第$i$张工单生产,需要编号为$1$的轩轩提供原材料,则在第$i$行输出“Yes”;否则在第$i$行输出“No”。注意输出不含引号。

    サンプル入力 1

    3 2 6
    1 2
    2 3
    1 1
    2 1
    3 1
    1 2
    2 2
    3 2

    サンプル出力 1

    No
    Yes
    No
    Yes
    No
    Yes

    サンプル入力 2

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

    サンプル出力 2

    No
    Yes
    No
    Yes
    Yes

    ヒント

    输入输出样例1说明

    • 编号为$1$的工人想生产第$1$阶段的零件,需要编号为$2$的工人提供原材料。
    • 编号为$2$的工人想生产第$1$阶段的零件,需要编号为$1$和$3$的工人提供原材料。
    • 编号为$3$的工人想生产第$1$阶段的零件,需要编号为$2$的工人提供原材料。
    • 编号为$1$的工人想生产第$2$阶段的零件,需要编号为$2$的工人生产第$1$阶段的零件,需要编号为$1$和$3$的工人提供原材料。
    • 编号为$2$的工人想生产第$2$阶段的零件,需要编号为$1$和$3$的工人生产第$1$阶段的零件,他/她们都需要编号为$2$的工人提供原材料。
    • 编号为$3$的工人想生产第$2$阶段的零件,需要编号为$2$的工人生产第$1$阶段的零件,需要编号为$1$和$3$的工人提供原材料。

    输入输出样例2说明

    • 编号为$1$的工人想生产第$1$阶段的零件,需要编号为$2$和$5$的工人提供原材料。
    • 编号为$1$的工人想生产第$2$阶段的零件,需要编号为$2$和$5$的工人生产第$1$阶段的零件,需要编号为$1,3,4$的工人提供原材料。
    • 编号为$1$的工人想生产第$3$阶段的零件,需要编号为$2$和$5$的工人生产第$2$阶段的零件,需要编号为$1,3,4$的工人生产第$1$阶段的零件,需要编号为$2,3,4,5$的工人提供原材料。
    • 编号为$1$的工人想生产第$4$阶段的零件,需要编号为$2$和$5$的工人生产第$3$阶段的零件,需要编号为$1,3,4$的工人生产第$2$阶段的零件,需要编号为$2,3,4,5$的工人生产第$1$阶段的零件,需要全部工人提供原材料。
    • 编号为$1$的工人想生产第$5$阶段的零件,需要编号为$2$和$5$的工人生产第$4$阶段的零件,需要编号为$1,3,4$的工人生产第$3$阶段的零件,需要编号为$2,3,4,5$的工人生产第$2$阶段的零件,需要全部工人生产第$1$阶段的零件,需要全部工人提供原材料。

    数据规模与约定

    共20个测试点,$1\leq u,v,a\leq n$。
    测试点1~4:$1\leq n,m\leq 1000,\quad q=3,\quad L=1$。
    测试点5~8:$1\leq n,m\leq 1000,\quad q=3,\quad 1\leq L\leq 10$。
    测试点9~12:$1\leq n,m,L\leq 1000,\quad 1\leq q\leq 100$。
    测试点13~16:$1\leq n,m,L\leq 1000,\quad 1\leq q\leq 10^5$。
    测试点17~20:$1\leq n,m,q\leq 10^5,\quad 1\leq L\leq 10^9$。