A Tree-Filled Tree Problem

Jiho had to write a tree problem, but he had already written one that uses trees in its solution. So this time he decided to write a problem whose statement is full of trees.

To write a good problem whose statement is full of trees, he needs to take many tree lectures and learn a lot of tree-related knowledge. Luckily, Gyeonggi Science High School, which loves trees, has $N$ good tree lectures. The $i$-th tree lecture runs from time $a_i$ to $b_i$, and attending it gives $1$ unit of tree knowledge. If two tree lectures do not overlap in time, Jiho can attend both and study more about trees to write a better tree problem. Also, if $a_i = b_j$ or $b_i = a_j$ for two lectures, they count as overlapping.

Some of the $N$ tree lectures are mandatory, and Jiho can freely sign up for the rest as long as they do not overlap in time. Find the maximum amount of tree knowledge Jiho can obtain.

Jiho does not yet know which tree lectures are mandatory. For each of the $M$ queries, a few mandatory tree lectures are given. For each query, print the maximum amount of tree knowledge Jiho can obtain.

The first line contains $N$ and $M$, separated by a space.

From the second line onward, the $i$-th of the next $N$ lines contains two integers $a_i$ and $b_i$, separated by a space, which are the start and end times of the $i$-th tree lecture.

The following $M$ lines each contain one query. Each query gives the number $s$ of mandatory tree lectures, followed by the $s$ lecture numbers $p_1, p_2, \cdots, p_s$, all separated by spaces.

Print $M$ lines. The $i$-th line contains the maximum amount of tree knowledge Jiho can obtain for the $i$-th query.

• $1 \leq N, M \leq 300\,000$
• $1 \leq a_i < b_i \leq 10^9$ ($1 \leq i \leq N$)
• (The sum of $s$ over all queries) $\leq 300\,000$
• In each query, $b_{p_i} < a_{p_{i+1}}$ ($1 \leq i < s$)
• In each query, $s>0$

Two different tree lectures may start and end at exactly the same time.

The word "tree" appears 36 times in this statement (38 times including the title).