P7965 [COCI 2021/2022 #2] Kutije

Matrin 有 $n$ 个箱子的玩具。箱子分别用序号 $1,2,3,\cdots,n$ 表示。初始状态下，每个箱子中有一个与箱子编号相同的玩具。 Matrin 邀请了 $m$ 位朋友来家玩玩具。他注意到，每一位朋友在玩完玩具之后，都会将原先位于 $i$ 号箱子内的玩具放入 $p_i$ 号箱内。 给定 $q$ 组询问，每次可随意邀请朋友并自由选择顺序，同时每位朋友可以邀请任意多次。问是否存在一种方案，使得 $a$ 号玩具最终被放入 $b$ 号箱子中。

第一行三个正整数 $n,m,q$，分别表示箱子 / 玩具、朋友和询问的数量。 接下来的 $m$ 行，每行 $n$ 个整数 $p_i$。数据保证 $p_i$ 是 $1 \sim n$ 的一个排列。 接下来的 $q$ 行，每行两个整数 $a,b$。

共 $q$ 行，每行输出一个字符串 $\texttt{DA}$（是）或 $\texttt{NE}$（否）。

**【样例 1 解释】** - 询问 $1$：初始状态下，$1$ 号玩具已经在 $1$ 号箱子内，故输出 $\texttt{DA}$。 - 询问 $2$：第二组询问：无符合题意的方案，输出 $\texttt{NE}$。 - 询问 $3$：邀请 $1$ 号朋友前来即可，输出 $\texttt{DA}$。 **【数据规模与约定】** **本题采用子任务捆绑测试。** - Subtask 1（15 pts）：$m=1$。 - Subtask 2（10 pts）：$1 \le n,m,q \le 100$；对于每组询问，若答案为 $\texttt{DA}$，则保证存在一种邀请朋友数量不超过 $2$ 的方案。 - Subtask 3（10 pts）：$1 \le n,m,q \le 100$。 - Subtask 4（35 pts）：无特殊限制。 对于 $100\%$ 的数据，$1 \le n,m \le 1000$，$1 \le q \le 5 \times 10^5$，$1 \le a,b \le n$。 **【提示与说明】** **题目译自 [COCI 2021-2022](https://hsin.hr/coci/) [CONTEST #2](https://hsin.hr/coci/contest2_tasks.pdf) _Task 2 Kutije_。** **本题分值按 COCI 原题设置，满分 $70$。**