DMOPC '22 Contest 3 P2 - New Components

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Anya wants to celebrate New Year's, however, Loid is only willing to do so if she studies hard for her exams. Initially, Anya is playing with a permutation P of N integers from 1 to N. In order to test her abilities, Loid gives her Q independent queries to answer. Each query is a set S of distinct indices in the permutation. For each index x in S, Anya must set the value of P_x to any integer y such that y is not in S, and 1 \le y \le N. Then, Anya creates a graph by drawing an undirected edge from i to P_i, for all 1 \le i \le N. The answer to the query is the maximum number of connected components she can obtain. Queries are independent, so the permutation is restored after every query. Unfortunately, Anya is not smart enough to solve this problem. Please help Anya cheat and pass the test!


2 \le N \le 10^6

1 \le P_i \le N

1 \le Q \le 10^6

1 \le |S| < N

P is a permutation of the integers 1, 2, \dots, N.

The elements of S are distinct.

The sum of |S| across all queries does not exceed 10^6.

Subtask 1 [30%]

For 1 \le i \le N-1, P_i=i+1, and P_N=1.

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains 2 space-separated integers N and Q.

The next line contains N space-separated integers, representing the permutation P.

The next 2Q lines contain the Q queries. The first line of each query is an integer |S|, the size of the set. The second line of each query contains |S| integers, representing the set S.

Output Specification

Output Q lines, where the ith line contains the maximum number of connected components obtainable for each query.

Sample Input

6 2
3 6 5 1 4 2
2 6
3 4 2

Sample Output


Explanation for Sample

In the first query, it can be shown that the only possible number of connected components obtainable is 1, for example by turning P into [3, 3, 5, 1, 4, 5].

In the second query, turning P into [3, 6, 1, 5, 4, 2] is optimal.


There are no comments at the moment.