CF165D Beard Graph

给定一个包含 $n$ 个顶点和 $n-1$ 条边的无向连通图，如果除了最多一个顶点外，其余所有顶点的度数均为 $2$ 或 $1$（即不超过一个顶点的度数大于 $2$），则称其为胡须图。顶点的度数表示和该顶点相连的边的数量。 每条边要么是黑色，要么是白色。所有边初始均为黑色。 现给定一张胡须图的描述，你需要处理下列类型的若干操作： - 将编号为 $i$ 的边涂成黑色。编号 $i$ 的边指输入顺序的第 $i$ 条边。保证进行该操作时第 $i$ 条边是白色。 - 将编号为 $i$ 的边涂成白色。保证进行该操作时第 $i$ 条边是黑色。 - 查询只经过黑色边，顶点 $a$ 和 $b$ 间的最短路径长度，或判断是否不存在这样的路径（路径长度为经过的边数）。 顶点从 $1$ 到 $n$ 编号，边从 $1$ 到 $n-1$ 编号。

输入的第一行包含一个整数 $n$（$2 \leq n \leq 10^5$）——图的顶点数。接下来 $n-1$ 行，每行两个整数 $v_{i}$，$u_{i}$（$1 \leq v_{i},u_{i} \leq n$，$v_{i} \neq u_{i}$），表示一条连接 $v_{i}$ 和 $u_{i}$ 的边。保证图连通、是胡须图、无自环、无重边。 之后一行为整数 $m$（$1 \leq m \leq 3 \cdot 10^5$）——操作数。接下来 $m$ 行，每行为一次操作。每次操作格式如下： - 若为操作类型 $1$，则该行为 $1\ id$，表示将编号为 $id$ 的边涂为黑色（$1 \leq id \leq n-1$）。 - 若为操作类型 $2$，则该行为 $2\ id$，表示将编号为 $id$ 的边涂为白色。 - 若为操作类型 $3$，则该行为 $3\ a\ b$，表示查询顶点 $a$ 到 $b$ 之间仅经过黑色边的最短距离（$1 \leq a, b \leq n$，$a$ 可等于 $b$）。 同一行的数字间用一个空格隔开。边编号顺序即输入顺序。

对于每个“查询顶点 $a$ 到 $b$ 间距离”的操作，输出一个结果，若仅沿黑色边无路则输出 $-1$。多个输出按出现顺序，用空格或换行分隔。

在第一个样例中，顶点 $1$ 与 $2$ 用编号 $1$ 的边连，顶点 $2$ 与 $3$ 用编号 $2$ 的边连。边 $2$ 尚未被重新染色前，每个顶点均可通过黑色边互达，$1$ 到 $3$ 的最短路径经过这两条边。 若将编号 $2$ 的边染成白色，顶点 $3$ 即被与其他顶点割离——此时仅通过黑色边已无法从 $3$ 到达其它顶点。 由 ChatGPT 5 翻译