首先，聪明的你应该把$duck$反过来读：就是“可达”。
所以这道题就是“可达性统计”的模板题。
只不过，这道题把数据加强到了 $10^5$，并且本题中的图可能存在环。
就是这两个问题，我们一个一个来处理。
对于图中存在环的问题，我们只需要 $\texttt{tarjan}$一下，缩点染色一下就行了，因为在一个环内的两个点肯定两两互相可达，我们把他染成一个颜色并没有问题，其他的操作正常进行，$\texttt{tarjan}$ 缩点肯定大家都会。
接着，我们要对付 $10^5$ 的数据。
对于简单版的可达性统计，我们是建了 bitset<1005> b[1005]，b[x][y] 代表的是否能从 $x$ 点到达 $y$ 点，我们用 $\texttt{bitset}$，是为了把第二维压成一个 01 串，从而降低空间。但是对于 $10^5$ 的数据我们把 $\texttt{bitset}$ 建出来：bitset<100005> b[100005]。算一下，上了 $1000\texttt{MiB}$，肯定不可取。
那怎么办呢？
这里就要用到一个很常用的，很重要的技巧：牺牲时间复杂度来补救空间复杂度！
因为我们发现，时间复杂度太优秀了，空间复杂度太菜了。于是我们想到一个类似分块的思想来解决这个问题。
我们可以把 $Ｑ$ 次询问分成 $k$ 段，每一段长为 $len$，然后一段一段地解决，一段一段地处理，我们将每一段询问中 $(u,v)$ 的 $v$ 做一个离散化操作，使得 $\texttt{bitset}$ 的第二维空间降下来，因为这一段最后真正有用的就这 $len$ 个点能否到达，至于其他点能否到达我们不在乎，将它们都看作编号为 0 即可。每一段询问都进行同样的操作，就可以通过本题。其实这样的方法也不叫分块，它就是把一个问题分成了几段，依次处理。
当然，在保证空间复杂度的前提下，$k$ 越小越好。
$code:$
#include<cmath>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<bitset>
#define reg register
using namespace std;
const int maxn=2e5+5;
const int mod=1e9+7;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
int n,m,Q;
int wugui=0;
int head1[maxn];
struct node
{
int to;
int nxt;
}edge[maxn];
void add(int x,int y)
{
wugui++;
edge[wugui].to=y;
edge[wugui].nxt=head1[x];
head1[x]=wugui;
}
int in[maxn];
queue<int> q;
vector<int> v[maxn];
int low[maxn];
int dfn[maxn];
int cnt=0;
int s[maxn];
int col[maxn];
int color=0;
int vis[maxn];
int index1=0;
struct Query
{
int x,y;
}ask[maxn];
//tarjan
void tarjan(int x)
{
low[x]=dfn[x]=++index1;
vis[x]=1;
s[++cnt]=x;
for(reg int i=0;i<(int)v[x].size();i++)
{
int t=v[x][i];
if(dfn[t]==0)
{
tarjan(t);
low[x]=min(low[x],low[t]);
}
else
{
if(vis[t]==1)
low[x]=min(low[x],dfn[t]);
}
}
if(dfn[x]==low[x])
{
int v;
color++;
do
{
v=s[cnt];
cnt--;
col[v]=color;
vis[v]=0;
}
while(v!=x);
}
}
bitset<20005> a[maxn];
int re_in[maxn];
int tot=0;
int b[maxn];
int id[maxn];
int Get(int x)
{
return lower_bound(s+1,s+1+tot,x)-s;
}
int order[maxn];
int ORDER=0;
void Work(int l,int r)
{
// re_sort & Get_id
tot=0;
int fuck=0;
for(reg int i=l;i<=r;i++)
b[++fuck]=col[ask[i].y];
sort(b+1,b+1+fuck);
b[0]=-1e9;
for(reg int i=1;i<=fuck;i++)
{
if(b[i]!=b[i-1])
s[++tot]=b[i];
}
// bitset_dp & topo
for(reg int i=1;i<=color;i++)
{
id[i]=Get(i);
if(s[id[i]]!=i)
id[i]=0;
a[i].reset();
if(re_in[i]==0)
{
q.push(i);
int x=id[i];
a[i][x]=1;
}
}
for(reg int j=1;j<=ORDER;j++)
{
int point=order[j];
int x=id[point];
a[point][x]=1;
for(reg int i=head1[point];i;i=edge[i].nxt)
{
int t=edge[i].to;
a[t] |= a[point];
}
}
// Get_ans
for(reg int i=l;i<=r;i++)
{
int x=col[ask[i].x];
int y=col[ask[i].y];
if(a[x][id[y]])
cout<<"Y";
else
cout<<"N";
}
}
int main()
{
//tarjan
n=read(),m=read(),Q=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
v[x].push_back(y);
}
for(int i=1;i<=n;i++)
{
if(dfn[i]==0)
tarjan(i);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<(int)v[i].size();j++)
{
int x=col[i];
int y=col[v[i][j]];
if(x==y)
continue;
in[x]++;
add(y,x);
}
}
//topo_sort
for(int i=1;i<=color;i++)
re_in[i]=in[i];
for(reg int i=1;i<=color;i++)
{
if(in[i]==0)
q.push(i);
}
while(!q.empty())
{
int point=q.front();
q.pop();
order[++ORDER]=point;
for(reg int i=head1[point];i;i=edge[i].nxt)
{
int t=edge[i].to;
in[t]--;
if(in[t]==0)
q.push(t);
}
}
// divide segments
for(int i=1;i<=Q;i++)
ask[i].x=read(),ask[i].y=read();
int len=20000;
int now=1;
while(true)
{
if(now+len-1<Q)
{
Work(now,now+len-1); // Get_ans
now=now+len;
}
else
{
Work(now,Q); // Get_ans
break;
}
}
return 0;
}