RYIP在线题库
首 页   >   习题练习   >   提交
Problem1368--加工零件

1368: 加工零件

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

【 Description 】

凯凯的工厂正在有条不紊地生产一种神奇的零件,神奇的零件的生产过程自然也很

神奇。工厂里有n位工人,工人们从1∼n编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带。

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

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

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



【提示】

【输入输出样例 1 说明】

http://ybt.ssoier.cn:8088/pic/1985a.gif

编号为 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

【输入输出样例 2 说明】

http://ybt.ssoier.cn:8088/pic/1985b.gif

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

编号为 1 的工人想生产第 2 阶段的零件,需要编号为 2 和 5 的工人生产第 1 阶段的零件,需要编号为 134 的工人提供原材料。

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

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

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


【 Input 】

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

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

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

【 Output 】

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

【 Sample Input 】

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

【 Sample Output 】

No
Yes
No
Yes
No
Yes

【HINT】

【数据规模与约定】

共 20 个测试点。

1≤uva≤n。

测试点 1~4,1≤nm≤1000,q=3,L=1。

测试点 5~8,1≤nm≤1000,q=3,1≤L≤10。

测试点 9~12,1≤nmL≤1000,1≤q≤100。

测试点 13~16,1≤nmL≤1000,1≤q≤10^5。

测试点 17~20,1≤nmq≤10^5,1≤L≤10^9。


【 Source/Category 】

CSP