← 返回题目列表

Codeforces · 175/F

F. 魔法门之侏儒

中文机器翻译题面 查看原题

Vasya 玩一款流行游戏《魔法门之侏儒》。

在这款游戏中,瓦西亚管理侏儒王国,该王国由几座城堡组成,通过双向道路连接。王国公路网具有特殊的形式。王国有m座主要城堡a1,a2,...,am,它们构成了善道。该路径由城堡 ai、ai + 1 (1 ≤ i < m) 之间的道路以及 am 和 a1 之间的道路组成。善道的城堡之间没有其他道路。

此外,对于每对相邻的善路城堡u和v,都恰好有一条邪恶捷径——一条沿着从第一个城堡(u)通向第二个城堡(v)的道路,除了顶点u和v外,与善路没有任何公共顶点。众所周知,王国里没有其他道路和城堡,也就是说,每条道路和每座城堡要么位于善路,要么位于邪恶之路捷径(城堡可以位于两者之中)。此外,与正道的城堡不同,没有两条邪道有共同的城堡。

王国里每周一开始都会出现一个非常坏的侏儒,他站在王国的一条道路上,并开始抢劫经过这条路的科洛万人。一条路可能会聚集多个非常糟糕的侏儒。瓦夏关心他的科洛凡人,所以有时他会将死亡使命从一座城堡发送到另一座城堡。

我们建议死亡任务应该从城堡 s 到达城堡 t。然后它会从 s 城堡移动到 t 城堡,消灭任务道路上所有非常糟糕的侏儒。瓦夏是如此强大,他的死亡使命可以摧毁途中任意数量的侏儒。不过瓦夏很善良,所以他总是选择s和t城堡之间的这条路,沿着这条路他会消灭最少数量的侏儒。如果有多条这样的路径,则 Vasya 会选择其中包含最少道路的路径。如果仍然存在多条这样的路径,Vasya 会选择其中字典顺序最小的一条。

帮助 Vasya 在《魔法门之侏儒》游戏中模拟王国的生活。

路径是一系列城堡,路径上的每对相邻城堡都通过道路连接。另外,路径 x1, x2, ... , xp 按字典顺序小于路径 y1, y2, ... , yq,如果 p < q 且 x1 = y1, x2 = y2, ... , xp = yp,或者存在这样的数字 r (r < p, r < q),即 x1 = y1, x2 = y2, ... , xr = yr 且 xr + 1 < yr + 1.

输入

第一行包含两个整数 n 和 m (3 ≤ m ≤ n ≤ 100000) — 分别是王国中的城堡数量和善道上的城堡数量。

第二行包含 m 个整数,它们是 Good Path 城堡的数量(城堡编号为 1 到 n),按照 Path 上出现的顺序,从某个城堡开始。所有 Good Path 城堡都各不相同。

以下 m 行中的每一行都描述了一条邪恶的捷径。首先一行包含一个整数 ki (3 ≤ ki ≤ 100000) — 相应的邪恶快捷方式上的城堡数量(以及好路上的两座城堡),后面跟着一个 ki 整数 — 按照给定快捷方式中出现的顺序排列的城堡数量。 《邪恶捷径》中的所有城堡都是不同的。保证捷径中的第一个和最后一个城堡位于好路径上,而邪恶捷径中的第一个城堡形成好路径,并且以与第二行表示路径相同的顺序呈现。

下一行包含一个整数 q (1 ≤ q ≤ 100000) — 王国生活中事件的数量。以下 q 行中的每一行都描述一个事件。事件由符号 cj 和两个数字或城堡 sj 和 tj 描述(城堡的字符和数字由单个空格分隔)。如果cj的字符等于“+”(加号),则意味着在城堡sj和tj之间的道路上出现了一个非常糟糕的侏儒(可能不是第一个)。如果 cj 等于“?” (一个问题),然后Vasya从城堡sj发送了一个死亡任务到城堡tj。保证对于每个请求“+”,城堡 sj 和 tj 之间的道路都存在。这些事件按时间顺序排列,从最早的事件开始。最初,路上并没有非常糟糕的侏儒。

所有行中的所有数字均以单个空格分隔。保证所有给定的“邪恶捷径”和“好路径”都符合问题陈述中给出的限制。

输出

对于每个查询“?”在一行上打印一个数字——被相应的死亡任务摧毁的非常糟糕的侏儒的数量。按时间顺序打印查询的答案。

示例

输入 #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

注意

在前四个请求之后的示例中,从城堡 1 到城堡 2 只有一条路径,其中不包含具有非常糟糕的侏儒的道路: 1 $$\rightarrow$$ 6 $$\rightarrow$$ 3 $$\rightarrow$$ 5 $$\rightarrow$$ 2。

当侏儒站在路上 (2, 5) 后,下一个死亡任务会沿着路径 1 $$\rightarrow$$ 2 移动,并摧毁路上 (1, 2) 上的侏儒。下一个死亡任务将遵循同样的道路,但已经没有侏儒了。

当又一个侏儒站在道路 (1, 2) 上后,下一个死亡任务会沿着路径 1 $$\rightarrow$$ 2 前进,并杀死该侏儒。