#P18279. Have You Seen This Subarray?

Have You Seen This Subarray?

Have You Seen This Subarray?

最初有一个长度为 nn 的数组 aa,满足 ai=ia_i=i。随后对它执行 mm 次交换操作:每次选择两个位置 i,ji,j,交换 aia_i 和 aja_j。

你需要回答 qq 个询问。每个询问给出一个数组 b1,b2,…,bkb_1,b_2,\ldots,b_k,求它第一次作为 aa 的一段连续子数组出现时,已经执行了多少次交换。元素的顺序必须完全一致。

保证每次交换的两个不同位置都是独立、均匀随机选取的。也保证每个询问的数组都曾在某个时刻作为连续子数组出现。

输入格式

第一行包含三个整数 n,m,qn,m,q。

接下来 mm 行,每行包含两个整数 i,ji,j(1≤i<j≤n1\le i<j\le n),表示一次交换。

接下来 qq 行描述询问。每行先给出一个整数 kk,然后给出 kk 个整数 b1,b2,…,bkb_1,b_2,\ldots,b_k。

输出格式

对每个询问,在单独一行输出它第一次出现之前已经执行的交换次数。

如果它在初始数组中就是连续子数组,输出 00。第 tt 次交换后的数组对应时刻 tt,因此答案在 [0,m][0,m] 内。题目保证存在答案,不需要输出不存在的情况。

数据范围

  • 1≤n,m,q≤1051\le n,m,q\le10^5;
  • 每次交换满足 1≤i<j≤n1\le i<j\le n;
  • 每个询问满足 1≤k≤n1\le k\le n,1≤bi≤n1\le b_i\le n;
  • 所有询问的 kk 之和不超过 10510^5。

输入只有一组数据。随机交换保证和每个询问一定出现的保证,都是原题条件。

样例

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

三个交换后的数组依次为:

  • [5,2,3,4,1,6][5,2,3,4,1,6];
  • [5,2,4,3,1,6][5,2,4,3,1,6];
  • [6,2,4,3,1,5][6,2,4,3,1,5]。

例如,[4,1][4,1] 首次出现于第 11 次交换后,而 [3,4,5][3,4,5] 在初始数组中就存在。