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

工厂里有 n� 位工人，工人们从 1∼n1∼� 编号。

某些工人之间存在双向的零件传送带。

保证每两名工人之间最多只存在一条传送带。

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

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

轩轩是 1 号工人。

现在给出 q� 张工单，第 i� 张工单表示编号为 ai�� 的工人想生产一个第 Li�� 阶段的零件。

轩轩想知道对于每张工单，他是否需要给别人提供原材料。

他知道聪明的你一定可以帮他计算出来！

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

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

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

1≤u,v,a≤n。

测试点 1∼4，1≤n,m≤1000，q=3，L=1。

测试点 5∼8，1≤n,m≤1000，q=3，1≤L≤10。

测试点 9∼12，1≤n,m,L≤1000，1≤q≤100。

测试点 13∼16，1≤n,m,L≤1000，1≤q≤10^5。

测试点 17∼20，1≤n,m,q≤10^5，1≤L≤10^9。