Public Judge

pjudge

Time Limit: 1 s Memory Limit: 512 MB Total points: 100 Hackable ✓

# 21674. 【NOIP Round #1】别急

统计

题目描述

小 A 和小 B 来到了古神的宫殿。

他们在墙上发现了 $2n$ 个不超过 $n$ 的正整数 $f_1,f_2,\ldots,f_n,g_1,g_2\ldots,g_n$。

他们在地上发现了 $m$ 块石板,第 $i$ 块石板上写了两个不超过 $n$ 的正整数 $x_i,y_i$。

根据传说,每过一秒, $x_i$ 就会变为 $f_{x_i}$,$y_i$ 就会变为 $g_{y_i}$。而当 $x_i=y_i$ 时(包括初始时),第 $i$ 块石板就会裂开。

小 A 想分别知道每块石板是否会裂开,但他觉得一直等下去太慢了。

小 B 让小 A 别急,但小 A 很急,你也很急,所以你要在一秒内帮小 A 找到答案。

输入格式

第一行包括两个正整数 $n,m$。

第二行包括 $n$ 个正整数 $f_1,f_2\ldots,f_n$。

第三行包括 $n$ 个正整数 $g_1,g_2\ldots,g_n$。

接下来 $m$ 行,第 $i$ 行包括两个正整数 $x_i,y_i$。

输出格式

共 $m$ 行,若第 $i$ 个石块最终会裂开就在第 $i$ 行输出 YES,否则输出 NO

样例

样例输入 1

4 3
2 3 4 2
2 4 4 1
1 2
1 4
3 3

样例输出 1

NO
YES
YES

样例解释 1

对于第一块石板,可以证明它永远不会裂开。

对于第二块石板,$(x_2,y_2)$ 的变化为 $(1,4)\rightarrow(2,1)\rightarrow(3,2)\rightarrow(4,4)\rightarrow\cdots$,于是它会在三秒之后裂开。

对于第三块石板,它会在一开始就裂开。

样例输入 2

10 10
3 8 7 3 7 6 4 1 9 10
3 3 2 6 7 6 5 5 10 10
1 5
10 4
10 2
7 6
8 7
3 4
10 5
5 5
2 6
8 5

样例输出 1

YES
NO
NO
NO
YES
NO
NO
YES
NO
YES

样例输入 / 输出 3

见下发文件中的 ex_wait3.in/ex_wait3.ans,该样例满足子任务 3 的特殊性质。

样例输入 / 输出 4

见下发文件中的 ex_wait4.in/ex_wait4.ans,该样例满足子任务 5 的特殊性质。

样例输入 / 输出 5

见下发文件中的 ex_wait5.in/ex_wait5.ans,该样例满足子任务 6 的特殊性质。

样例输入 / 输出 6

见下发文件中的 ex_wait6.in/ex_wait6.ans,该样例满足子任务 7 的特殊性质。

数据范围

本题采用捆绑测试。

对于所有数据 $1\le n,m\le 10^5,1\le f_i,g_i,x_i,y_i\le n$。

子任务编号 $n,m\le$ $f$ $g$ 子任务分值
1 $10$ - - 3
2 $100$ 7
3 $1000$ 11
4 $10^5$ * * 5
5 A A 17
6 B 17
7 B 17
8 - - 23

对于某个子任务,若其表格中 $h$ ($h$ 为 $f$ 或 $g$)这一列为:

  • A,则满足 $\forall 1\le i< j\le n,h_i\ne h_j$。
  • B,则满足 $\forall 1\le i\le n,h_i\le i$。
  • *,则该子任务(子任务 4)满足 $\forall 1\le i\le n,f_i=g_i$。
  • -,则无特殊限制。