E-permutation
Time limit2sMemory limit256 MB
Given a permutation p and the swap of positions 1 and 2, decide for each query whether position a can reach position b by composing these two operations any number of times.
- Level
Medium7 of 10
- Topics
- Graph, Union-find, Implementation, Math
- Solved
- No attempts yet
Problem
An e-permutation is a permutation z of the numbers from 1 to n that swaps the first two elements: z = [2, 1, 3, 4, ..., n].
You are given an e-permutation z and a permutation p = [p1, p2, ..., p**n] of the numbers from 1 to n. Consider n distinct objects placed at positions numbered from 1 to n. The objects can be moved according to permutations: after applying a permutation q, the object at position j moves to position qj for every j from 1 to n.
You are given m pairs of integers ai and bi. For each i, determine whether the object that was at position ai can be moved to position bi using only the permutation p and the e-permutation z. To reach the goal, you may apply p and z in any order and any number of times.
For example, if n = 4 and p = [1, 4, 3, 2], then the element at position 4 can be moved to position 1 (for instance, apply p, after which the object at position 4 ends up at position 2, and then apply z), while the element at position 3 cannot be moved to position 4, since both p and z leave it in place.
Input
The first line contains two integers n and m: the number of elements in the permutation and the number of queries (2 ≤ n ≤ 105, 1 ≤ m ≤ 105). The next line contains n integers pi, the permutation p. Each of the following m lines contains two integers ai and bi (ai and bi lie in the range from 1 to n).
Output
For each query, print Yes on a separate line if the object at position ai can be moved to position bi, otherwise print No.