1448: 加工零件（2019 CCF CSP-J2）
时间限制: 1 Sec 内存限制: 256 MB提交: 2 解决: 1
[提交] [状态] [讨论版] [命题人:]
题目描述
凯凯的工厂正在有条不紊地生产一种神奇的零件，神奇的零件的生产过程自然也很神奇。工厂里有n位工人，工人们从1∼n 编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带。
如果x号工人号工人想生产一个被加工到第L(L>1)阶段的零件，则所有与x号工人有传送带直接相连的工人，都需要生产一个被加工到第L−1阶段的零件（但x号工人自己无需生产第L−1阶段的零件）。
如果x号工人想生产一个被加工到第1阶段的零件，则所有与x号工人有传送带直接相连的工人，都需要为x号工人提供一个原材料。
轩轩是1号工人。现在给出q张工单，第i张工单表示编号为ai的工人想生产一个第Li阶段的零件。轩轩想知道对于每张工单，他是否需要给别人提供原材料。他知道聪明的你一定可以帮他计算出来！
如果x号工人号工人想生产一个被加工到第L(L>1)阶段的零件，则所有与x号工人有传送带直接相连的工人，都需要生产一个被加工到第L−1阶段的零件（但x号工人自己无需生产第L−1阶段的零件）。
如果x号工人想生产一个被加工到第1阶段的零件，则所有与x号工人有传送带直接相连的工人，都需要为x号工人提供一个原材料。
轩轩是1号工人。现在给出q张工单，第i张工单表示编号为ai的工人想生产一个第Li阶段的零件。轩轩想知道对于每张工单，他是否需要给别人提供原材料。他知道聪明的你一定可以帮他计算出来！
输入
第一行两个正整数 n, m 和 q，分别表示工人的数目、传送带的数目和工单的数目。 接下来m行，每行两个正整数u和v，表示编号为u 和v的工人之间存在一条零件传输带。保证u≠v。
接下来q行，每行两个正整数a和L，表示编号为a的工人想生产一个第L阶段的零件。
接下来q行，每行两个正整数a和L，表示编号为a的工人想生产一个第L阶段的零件。
输出
共q行，每行一个字符串 “Yes” 或者 “No”。如果按照第i张工单生产，需要编号为1的轩轩提供原材料，则在第i行输出“Yes”；否则在第i行输出“No”。注意输出不含引号。
样例输入 Copy
3 2 6
1 2
2 3
1 1
2 1
3 1
1 2
2 2
3 2
样例输出 Copy
No
Yes
No
Yes
No
Yes
提示
见选手目录下的 work/work1.in 和 work/work1.ans。
【输入输出样例 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】
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
见选手目录下的 work/work2.in 和 work/work2.ans。
【输入输出样例 2 说明】
【输入输出样例 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阶段的零件，需要全部工人提供原材料。
【输入输出样例3】
见选手目录下的work/work3.in和work/work3.ans。
【数据规模与约定】
共20个测试点。
1 ≤ u, v, a ≤n。
测试点 1~4，1 ≤ n,m≤ 1000，q = 3，L = 1。
测试点 5~8，1 ≤n,m≤ 1000，q= 3，1 ≤L≤ 10。
测试点 9~12，1 ≤n,m,L≤ 1000，1 ≤ q≤ 100。
测试点 13~16，1 ≤n,m,L≤ 1000，1 ≤q≤ 105 。
测试点 17~20，1 ≤n,m,q≤ 105 ，1 ≤L≤ 109。
【输入输出样例 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】
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
见选手目录下的 work/work2.in 和 work/work2.ans。
【输入输出样例 2 说明】
【输入输出样例 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阶段的零件，需要全部工人提供原材料。
【输入输出样例3】
见选手目录下的work/work3.in和work/work3.ans。
【数据规模与约定】
共20个测试点。
1 ≤ u, v, a ≤n。
测试点 1~4，1 ≤ n,m≤ 1000，q = 3，L = 1。
测试点 5~8，1 ≤n,m≤ 1000，q= 3，1 ≤L≤ 10。
测试点 9~12，1 ≤n,m,L≤ 1000，1 ≤ q≤ 100。
测试点 13~16，1 ≤n,m,L≤ 1000，1 ≤q≤ 105 。
测试点 17~20，1 ≤n,m,q≤ 105 ，1 ≤L≤ 109。