#1471. CSP-模拟赛001-T4

CSP-模拟赛001-T4

题目描述

阿尔法星球有一个神奇的零件工厂, 这个工厂生产零件的过程很神奇。厂里共有 nn 个工人,分别编号为 1n1 \sim n 号。部分工人之间存在传送带,可以双向传送零件。

零件的加工分为很多阶段,记作 11 阶段、22 阶段、 33 阶段...

当第 ii 号工人准备加工的 t (t>1)t~(t > 1) 阶段的零件时,所有与第 ii 号工人通过传送带直接连接的工人,都必须先加工 t1t-1 阶段的零件,并传给第 ii 号工人(注意:第 ii 号工人自己无需进行 t1t-1 阶段的加工)。

如果第 ii 号工人想加工 11 阶段的零件时,所有与第 ii 号工人通过传送带直接连接的工人,都必须为第 ii 号工人提供一个原材料。

现有 qq 张工单,每张工单都指定了第 xx 号工人需要加工 tt 阶段的零件。

仔仔是这个工厂的第 11 号工人。他想知道对于每张工单,是否需要他提供原材料。

输入格式

第一行为三个正整数 nmn,mqq,即工人的个数、传送带的个数与工单的个数。

接下来 mm 行,每行为两个正整数 uuvv,即编号 uu 与编号 vv 的工人之间存在一条传送带。数据保证 uvu \neq v

接下来 qq 行,每行两个正整数 xxtt,表示编号为 xx 的工人需要加工 tt 阶段的零件。

输出格式

qq 行,每行一个字符串 Yes 或者 No。如果对于任意一张工单,需要编号为 1 的仔仔提供原材料,输出 Yes;否则输出 No

样例 #1

样例输入 #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

样例输入 #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 说明 image 11 号工人要加工 11 阶段的零件,则 22 号工人需要提供原材料。

22 号工人要加工 11 阶段的零件,则 11 号与 33 号工人需要提供原材料。

33 号工人要加工 11 阶段的零件,则 22 号工人需要提供原材料。

11 号工人要加工 22 阶段的零件,则 22 号工人需要加工 11 阶段的零件,而 11 号和 33 号工人需要为其提供原材料。

22 号工人要加工 22 阶段的零件,则 11 号和 33 号工人需要先加工 11 阶段的零件,而 22 号工人需要为两人提供原材料。

33 号工人要加工 22 阶段的零件,则 22 号工人需要加工 11 阶段的零件,而 11 号和 33 号工人需要提供原材料。

数据规模与约定 1u,v,xn1 \leq u, v, x \leq n1n,m,q1051 \leq n, m, q \leq 10^51t1091 \leq t \leq 10^9