[SGU384] Country / 国家

题目描述

很久以前，一个遥远的王国里有一位非常聪明的国王。他想改革国家的道路系统。

把道路系统看成一个无向简单图：城市是顶点，道路是边，不存在自环和重边。国王进行了一次特殊的数学改革，使得改革刚完成时满足：

对任意两个不同的城市，恰好存在一个城市同时与它们相邻。

改革之后，随着时间推移，一些道路会被摧毁。政府希望随时知道任意两个城市之间当前的最短距离。

你需要处理两类操作：

• DELETE x：删除最初输入的第 $x$ 条道路；
• LENGTH x y：询问城市 $x$ 到城市 $y$ 当前的最短路长度。

若两座城市已经不连通，输出 -1。

输入格式

第一行包含两个整数 $n,m$，表示改革刚完成时的城市数和道路数，其中 $3\le n\le10^5$。

原题没有单独给出 $m$ 的上界。由题目的特殊性质可以推出，合法的初始图一定是若干个三角形共用一个中心点的“风车图”，因此必有 $m=3(n-1)/2$。所以有效输入中 $n$ 必为奇数，并且 $3\le m\le149997$。

接下来 $m$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 条道路连接城市 $x_i,y_i$。城市编号为 $1\sim n$。

之后直到文件结束为止，每行是一条操作：

• DELETE x：删除最初输入的第 $x$ 条道路；每条道路至多被删除一次；
• LENGTH x y：询问当前城市 $x$ 到城市 $y$ 的最短路长度。

操作总数不超过 $2\times10^5$。

输出格式

对于每个 LENGTH 操作输出一行：

• 若可达，输出当前最短路长度；
• 否则输出 -1。

样例

3 3
1 2
2 3
3 1
LENGTH 1 2
DELETE 1
LENGTH 1 2
LENGTH 2 3
DELETE 3
LENGTH 1 2

1
2
1
-1