지문이 트리로 가득 찬 트리 문제

지호는 트리 문제를 내야 했지만, 이미 트리를 쓰는 트리 문제를 출제했다. 그래서 이번에는 지문이 트리로 가득 찬 트리 문제를 내기로 했다.

지문이 트리로 가득 찬 좋은 트리 문제를 내려면 다양한 트리 강의를 많이 들어 트리에 대한 트리스러운 지식을 익혀야 한다. 다행히 트리를 사랑하는 경기과학고에는 좋은 트리 강의가 $N$개 있다. $i$번째 트리 강의는 시각 $a_i$부터 $b_i$까지 진행되며, 이 강의를 들으면 트리 지식을 $1$만큼 얻는다. 두 트리 강의의 시간이 겹치지 않으면 두 강의를 모두 들어 트리를 더 공부하고 더 좋은 트리 문제를 만들 수 있다. 단, $a_i = b_j$ 또는 $b_i = a_j$이면 두 강의는 겹치는 것으로 본다.

$N$개의 트리 강의 중 일부는 필수로 수강해야 하고, 나머지는 시간이 겹치지 않는 범위에서 자유롭게 신청해 들을 수 있다. 지호가 얻을 수 있는 트리 지식의 최댓값을 구하라.

지호는 아직 어떤 트리 강의가 필수인지 모른다. $M$개의 쿼리마다 필수 강의 몇 개가 주어지면, 각 쿼리에 대해 지호가 얻을 수 있는 트리 지식의 최댓값을 구하라.

첫 번째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$개의 줄 중 $i$번째 줄에는 $i$번째 트리 강의의 시작 시각 $a_i$와 종료 시각 $b_i$가 공백으로 구분되어 주어진다.

그다음 $M$개의 줄에 한 줄에 하나씩 쿼리가 주어진다. 각 쿼리에는 필수로 수강해야 하는 강의의 개수 $s$와 강의 번호 $p_1, p_2, \cdots, p_s$가 공백으로 구분되어 주어진다.

첫 번째 줄부터 $M$개의 줄에 걸쳐 $i$번째 줄에 $i$번째 쿼리에서 지호가 얻을 수 있는 트리 지식의 최댓값을 출력한다.

• $1 \leq N, M \leq 300\,000$
• $1 \leq a_i < b_i \leq 10^9$ ($1 \leq i \leq N$)
• (모든 쿼리에서 $s$의 합) $\leq 300\,000$
• 각 쿼리에서 $b_{p_i} < a_{p_{i+1}}$ ($1 \leq i < s$)
• 각 쿼리에서 $s>0$

서로 다른 두 트리 강의가 정확히 같은 시각에 시작하고 끝날 수도 있다.

이 문제의 지문에는 단어 '트리'가 총 36번(제목까지 38번) 나온다.