매혹적인 과정

시간 제한4초메모리 제한1024 MB

요약

1부터 N까지의 수에 대해 함수 f와 g를 동시에 적용할 때, 시작값 x와 y가 언젠가 같아지는지 쿼리마다 판단합니다.

문제

율리아는 칠판에 수 $x$ 를 적었고, 자하르는 $y$ 를 적었다. 1분마다 두 사람은 동시에 자기 수를 지우고 새 수를 적는다. 율리아의 수가 $i$ 이면 $f_i$ 가 된다. 자하르의 수가 $i$ 이면 $g_i$ 가 된다.

두 수가 같아지면 과정이 멈춘다. $x=y$ 이면 바로 멈추고, 나중에 멈출 수도 있으며, 영원히 멈추지 않을 수도 있다. 각 $x$ , $y$ 쌍에 대해 과정이 언젠가 끝나는지 판단하라.

첫 줄에 정수 $N$ 과 $Q$ 가 주어진다 ( $1 \le N, Q \le 10^5$ ).

둘째 줄에 정수 $f_1, \ldots, f_N$ 이 주어진다.

셋째 줄에 정수 $g_1, \ldots, g_N$ 이 주어진다.

이어지는 $Q$ 개의 줄에는 시작 수 $x_j$ 와 $y_j$ 가 주어진다. 모든 값은 1 이상 $N$ 이하의 정수이다.

$j$ 번째 질의에 대해, $x_j$ 와 $y_j$ 에서 시작한 과정이 끝나면 YES를, 그렇지 않으면 NO를 출력한다.