## DMOPC '22 Contest 3 P2 - New Components

View as PDF

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

Author:
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 of integers from to . In order to test her abilities, Loid gives her independent queries to answer. Each query is a set of distinct indices in the permutation. For each index in , Anya must set the value of to any integer such that is not in , and . Then, Anya creates a graph by drawing an undirected edge from to , for all . 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!

#### Constraints

is a permutation of the integers .

The elements of are distinct.

The sum of across all queries does not exceed .

For , , and .

#### Input Specification

The first line contains space-separated integers and .

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

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

#### Output Specification

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

#### Sample Input

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

#### Sample Output

1
3

#### Explanation for Sample

In the first query, it can be shown that the only possible number of connected components obtainable is , for example by turning into .

In the second query, turning into is optimal.