#788. 加工零件

加工零件

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

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

输入格式

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

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

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

输出格式

q\red{q} 行,每行一个字符串 Yes\red{Yes}或者No\red{No}。如果按照第 i\red{i} 张工单生产,需要编号为 1\red{1} 的轩轩提供原材料,则在第 i\red{i} 行输出 Yes\red{Yes};否则在第 i\red{i} 行输出 No\red{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 说明】

img

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

编号为 2\red{2} 的工人想生产第 1\red{1} 阶段的零件,需要编号为 1\red{1}3\red{3} 的工人提供原材料。

编号为 3\red{3} 的工人想生产第 1\red{1} 阶段的零件,需要编号为 2\red{2} 的工人提供原材料。

编号为 1\red{1} 的工人想生产第 2\red{2} 阶段的零件,需要编号为 2\red{2} 的工人生产第 1\red{1} 阶段的零件,需要编号为 1\red{1}3\red{3} 的工人提供原材料。

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

编号为 3\red{3} 的工人想生产第 2\red{2} 阶段的零件,需要编号为 2\red{2} 的工人生产第 1\red{1} 阶段的零件,需要编号为 1\red{1}3\red{3} 的工人提供原材料。

【输入输出样例 2 说明】

img

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

编号为 1\red{1} 的工人想生产第 2\red{2} 阶段的零件,需要编号为 2\red{2}5\red{5} 的工人生产第 1\red{1} 阶段的零件,需要编号为 1,3,4\red{1,3,4} 的工人提供原材料。

编号为 1\red{1} 的工人想生产第 3\red{3} 阶段的零件,需要编号为 2\red{2}5\red{5} 的工人生产第 2\red{2} 阶段的零件,需要编号为 1,3,4\red{1,3,4} 的工人生产第 1\red{1} 阶段的零件,需要编号为 2,3,4,5\red{2,3,4,5} 的工人提供原材料。

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

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

提示

20\red{20} 个测试点。

1u,v,an\red{1 \le u,v,a \le n}

测试点 14\red{1 \sim 4}1n,m1000\red{1 \leq n, m \leq 1000}q=3\red{q = 3}L=1\red{L = 1}

测试点 58\red{5 \sim 8}1n,m1000\red{1 \leq n, m \leq 1000}q=3\red{q = 3}1L10\red{1 \leq L \leq 10}

测试点 912\red{9 \sim 12}1n,m,L1000\red{1 \leq n, m, L \leq 1000}1q100\red{1 \leq q \leq 100}

测试点 1316\red{13 \sim 16}1n,m,L1000\red{1 \leq n, m, L \leq 1000}1q105\red{1 \leq q \leq 10^5}

测试点 1720\red{17 \sim 20}1n,m,q105\red{1 \leq n, m, q \leq 10^5}1L109\red{1 \leq L \leq 10^9}

2019年CSP-J第二轮重现

未参加
状态
已结束
规则
IOI
题目
4
开始于
2023-10-11 10:00
结束于
2023-10-20 14:00
持续时间
220 小时
主持人
参赛人数
34