本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-12-17 20:20:20

ZGC AK IOI!

$\color{green}\text{AC算法：}$ dfs

这道题可以发现，其实就是在求 $1$ 到要生产零件的工人 $a$的最短路，这个最短路的意思就是经过多少轮之后轮到轩轩（$1$ 号）提供零件。显然，如果最短路 $\le l$，那么肯定会让轩轩提供原材料。
但是这样随便画个图就hack掉了，最后分析这个图，可以发现要开两个数组，分别存最短路为奇数和最短路为偶数的。分开之后即可通过。

放上我几个月前的代码：

#define lmnjuruo "这题的难度对于lmn蒟蒻来说为IOI\/IOI+"
#define zgcshenxian "这题的难度对于zgc神仙来说为入门-"
#include <iostream>\/\/cin,cout
#include <cstring>\/\/string类
#include <cstdio>\/\/scanf,printf
#include <cstdlib>\/\/freopen,system等
#include <string>\/\/string类
#include <algorithm>\/\/算法库
#include <cmath>\/\/数学库
#include <iomanip>\/\/输出控制
#include <vector>\/\/容器系列
#include <set>\/\/不常用
#include <map>\/\/hash映射
#include <deque>\/\/双向容器
#include <queue>\/\/优先队列
#include <bitset>\/\/二进制
#include <ctime>
#define PI 3.14\/\/圆周率
#define inf 0x3f3f3f3f\/\/无穷大
#define ll long long\/\/不开long long见祖宗
#define ull unsigned long long
#define reg register\/\/寄存器存放
#define O2 ios::sync_with_stdio(false)\/\/加速cin
#define ZGC_AKIOI "100%"
#define LHX_AKIOI "100%"
#define DY_AKIOI "100%"
#define DCY_AKIOI "100%"
#define ZGC "邹神过河拆黑题，顺手AKIOI"
#define lmn "lmn蒟蒻过河被红题挡，顺手爆零模拟赛"
#define lmntrl "lmn蒟蒻爆零CSP-J2021"
using namespace std;
inline int read()\/\/快读
{
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-')
		{
			f=-1;
		}
		ch=getchar();
	}
	while(isdigit(ch))
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void write(int x)
{
    char F[200];
    int tmp=x>0?x:-x ;
    if(x<0)putchar('-') ;
    int cnt=0 ;
       while(tmp>0)
       {
           F[cnt++]=tmp%10+'0';
           tmp\/=10;
       }
       while(cnt>0)putchar(F[--cnt]) ;
}
const int maxn=1e5+5;
int n,m,q;
vector<int> edge[maxn];
int disou[maxn],disji[maxn];
void bfs()
{
	memset(disou,0x3f3f3f3f,sizeof(disou));
	memset(disji,0x3f3f3f3f,sizeof(disji));
	queue< pair<int,int> > que;
	for(int i=0;i<edge[1].size();i++)
	{
		int to=edge[1][i];
		disji[to]=1;
		que.push(make_pair(1,to));
	}
	while(!que.empty())
	{
		int u=que.front().second;
		int dis=que.front().first;
		que.pop();
		for(int i=0;i<edge[u].size();i++)
		{
			int to=edge[u][i];
			if(dis&1)\/\/更新答案后当前为偶数 
			{
				if(disou[to]>dis+1)
				{
					disou[to]=dis+1;
					que.push(make_pair(dis+1,to));
				}
			}
			else
			{
				if(disji[to]>dis+1)
				{
					disji[to]=dis+1;
					que.push(make_pair(dis+1,to));
				}
			}
		}
	}
}
int main()
{
	O2;
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	bfs();
	for(int i=1;i<=q;i++)
	{
		int a,l;
		cin>>a>>l;
		if(l&1)
		{
			if(disji[a]<=l)puts("Yes");
			else puts("No");
		}else
		{
			if(disou[a]<=l)puts("Yes");
			else puts("No");
		}
	} 
	return 0;
}