Captivating process

Time limit4sMemory limit1024 MB

Summary

Given functions f and g on 1 to N, for each query (x, y) decide whether applying both functions in lockstep ever makes the two values equal.

Level: Hard8 of 10
Topics: Graph, Number theory, Math
Solved: No attempts yet

Problem

Yulia wrote the number $x$ on the blackboard, and Zakhar wrote $y$ . Once every minute, they erase their numbers at the same time and write new numbers. If Yulia's number is $i$ , it becomes $f_i$ . If Zakhar's number is $i$ , it becomes $g_i$ .

They stop when their numbers match. This can happen right away if $x=y$ , later, or never. For each pair $x$ and $y$ , determine whether the process ever ends.

Input

The first line contains two integers $N$ and $Q$ ( $1 \le N, Q \le 10^5$ ).

The second line contains $N$ integers $f_1, \ldots, f_N$ .

The third line contains $N$ integers $g_1, \ldots, g_N$ .

Each of the following $Q$ lines contains the starting numbers $x_j$ and $y_j$ . All values are integers from 1 to $N$ .

Output

For each query $j$ , print YES if the process starting from $x_j$ and $y_j$ ends, and NO otherwise.

Examples2

Example 1
Input
```
3 2
2 3 1
2 3 1
1 2
1 1
```
Expected output
```
NO
YES
```
Example 2
Input
```
4 2
2 3 4 2
2 4 4 1
1 2
1 4
```
Expected output
```
NO
YES
```