侏儒魔法门 (gnomes)

题目描述

Y 同学统治着一个拥有 $n$ 个城堡的侏儒王国。在这些城堡中，有 $m$ 个关键的主要城堡，其编号序列为 $a_1, a_2, \dots, a_m$。

王国中的道路分为“好路”与“坏路”，且均为无向边：

• 好路：对于每一对相邻的主要城堡 $(a_i, a_{i+1})$（其中规定 $a_{m+1} = a_1$），都存在一条直接连接它们的好路。
• 坏路：对于每一对相邻的主要城堡 $(a_i, a_{i+1})$，还存在一条连接它们的坏路。每条坏路是由若干城堡构成的简单路径。

道路网络满足以下严谨的结构特性：

1. 坏路的起点和终点必然是两个由好路直接相连的主要城堡。
2. 除起点和终点外，坏路上的其他中间城堡均不是主要城堡。
3. 任意一个非主要城堡恰好属于一条坏路。
4. 王国中的每一个城堡都至少位于一条坏路上（主要城堡可能同时属于好路和坏路）。

起初，所有道路都是安全的，不包含任何障碍。随后会发生 $q$ 次事件，包含以下两种类型：

• + u v：在城堡 $u$ 与 $v$ 之间的直接道路上增加一个障碍物。保证 $u, v$ 之间在原图中存在直接相连的边。一条边上可以堆积多个障碍物。
• ? u v：Y 同学需要派出一支队伍从城堡 $u$ 前往 $v$。队伍会选择一条最优路径，并清理该路径上所有的障碍物。

最优路径的定义如下（优先级依次递减）：

1. 路径上障碍物的总数最少。
2. 在障碍物总数最少的前提下，路径经过的边数最少。
3. 在上述条件均相等的前提下，路径经过的顶点序列的字典序最小。

请输出每次询问时最优路径上的初始障碍物总数。由于询问不独立，一旦选定最优路径并移动，该路径上所有边上的障碍物数量将立即归零。

输入格式

第一行包含两个整数 $n, m$，分别表示城堡总数和主要城堡的数量。

第二行包含 $m$ 个整数 $a_1, a_2, \dots, a_m$，表示主要城堡的编号。

接下来的 $m$ 行，第 $i$ 行首先输入一个整数 $k_i$，表示连接 $a_i$ 和 $a_{i+1}$（当 $i=m$ 时为 $a_m$ 和 $a_1$）的坏路所包含的节点总数，随后紧跟 $k_i$ 个整数，按顺序描述这条坏路上的城堡编号序列。

下一行包含一个整数 $q$，表示操作次数。

接下来的 $q$ 行，每行描述一个操作：

• + u v：表示在 $u, v$ 之间的边上增加一个障碍物。
• ? u v：表示查询从 $u$ 到 $v$ 的最优路径，输出其障碍物总数并清除路径上的所有障碍物。

输出格式

对于每个 ? 操作，输出一行一个整数，表示该次最优路径上的初始障碍物总数。

样例

样例输入 #1

6 3
1 2 3
3 1 4 2
3 2 5 3
3 3 6 1
10
+ 1 2
+ 4 2
+ 1 3
+ 2 3
? 1 2
+ 2 5
? 1 2
? 1 2
+ 1 2
? 1 2

样例输出 #1

0
1
0
1

数据范围与约定

对于 $100\%$ 的数据，保证 $3 \le m \le n \le 10^5$，$1 \le q \le 10^5$，所有城堡编号在 $1$ 到 $n$ 之间。

特殊性质 A：保证 $m = n$，即所有城堡均为主要城堡，图中不存在任何中间节点。 特殊性质 B：保证所有的查询操作 ? u v 中的起点 $u$ 和终点 $v$ 均为主要城堡。