CF175F Gnomes of Might and Magic
题目描述
Vasya 最近正在玩一款叫作`迷你世界之侏儒魔法门`的游戏。
游戏中 Vasya 管理着迷你世界侏儒王国，王国中总共有 $n$ 个城堡，其中有 $m$ 个主要的城堡，中间用好路链接，第 $i$ 条好路连接着 $a_i$ 与 $a_{i+1}$，特别的，第 $m$ 条好路连接 $a_m$ 与 $a_1$，除了这 $m$ 条“好路”，城堡与城堡之间没有其他“好路”。
相应的，每条好路连接的两个端点都引出去一条坏路，这个坏路保证：
1. 坏路的开头和结尾一定是有好路连接的两个城堡。
2. 坏路除开头和结尾外的城堡都不是主要城堡。
3. 没有任何一个非主要城堡被两条坏路经过。
4. 每个城堡都在坏路上，其中有一些在好路上。
好路和坏路都是无向边。
每个时刻，都会有某一条道路上出现了张献忠，如果有人经过这条道路，那么张献忠就会把那个人图图了，Vasya 作为这个国家的领导人，发现这样不行，决定派出刘进忠从 $S$ 点前往 $T$ 点，刘进忠走到哪图到哪，他会选择一条从 $S$ 点到 $T$ 点的路径使得走这条路径图图的张献忠最少，如果有多条路径，选择长度最小的，如果有多条路径，选择字典序最小的。
注意：每次询问不独立。
输入格式
第一行，两个整数 $n$ 和 $m$ 表示王国中共有多少城堡以及其中主要城堡的数量。
第二行，$n$ 个整数 $a_i$，表示主要城堡的编号。
后面 $m$ 行，第 $i$ 行首先输入一个整数 $k_i$，表示这条坏路的长度，然后接 $k_i$ 个整数来描述这条坏路。
然后一个整数 $q$ 表示询问或修改的次数。
后面 $q$ 行，每行一个操作，形如：
1. `+ u v`，表示从 $u$ 到 $v$ 的边中多出现了一个张献忠。
2. `？ u v`，表示求出从 $u$ 图到 $v$，取到的最合法的路径中图图的侏儒数量，并动手把这条路径上的所有侏儒图图干净。（具体要求看题面）
输出格式
对于每个 $?$ 操作，输出答案。
翻译者：hmya
说明/提示
In the example after the first four requests there is only one path from castle 1 to castle 2, which does not contain roads with very bad gnomes: 1  6  3  5  2.
After a gnome stood on the road (2, 5), the next Mission of Death moves along path 1  2, and destroys the gnome, who was on the road (1, 2). The next Mission of Death follows the same path which is already free of gnomes.
After yet another gnome stood on the road (1, 2), the next Mission of Death goes on the path 1  2, and kills the gnome.