题目描述

给定两棵相同的无向树 $G$ 和 $H$，每棵树包含 $n$ 个顶点。两棵树被称为相同，当且仅当对于所有顶点对 $(u,v)$，$G$ 中存在边 $(G_u,G_v)$ 当且仅当 $H$ 中存在边 $(H_u,H_v)$。

某些顶点可以通过无向边连接到另一棵树中的对应顶点。特别地，叶子顶点 $G_v$ 可以直接连接到顶点 $H_v$。如果叶子顶点 $G_v$ 直接连接到 $H_v$，则称顶点 $v$ 为启用状态，否则为禁用状态。

初始时，所有叶子顶点均为禁用状态。需要处理以下两种查询：

1. $1$ $v$ —— 切换顶点 $v$ 的状态（若当前为禁用则改为启用，反之亦然）；
2. $2$ $u$ $v$ —— 输出从顶点 $G_u$ 到顶点 $H_v$ 的最短路径长度。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($3 \le n \le 2 \cdot 10^5$; $1 \le q \le 2 \cdot 10^5$) —— 分别表示顶点数和查询数。

接下来 $n-1$ 行，每行包含两个整数 $u$, $v$ $(1 \le u,v \le n)$ —— 描述树的边 $(G_u,G_v)$ 和 $(H_u,H_v)$。

接下来 $q$ 行，每行描述一个查询。查询有两种形式：

• $1$ $v$ $(1 \le v \le n)$ —— 切换顶点 $v$ 的状态；
• $2$ $u$ $v$ $(1 \le u,v \le n)$ —— 查询从 $G_u$ 到 $H_v$ 的最短路径长度。

输出格式

对于每个第二类查询，输出一个整数表示最短路径长度。若路径不存在，输出 $\texttt{-1}$。

7 11
1 2
2 3
1 4
2 5
4 6
4 7
1 6
1 3
2 1 6
2 1 2
1 7
2 5 4
2 6 3
1 6
1 3
1 5
2 6 3

2
3
5
4
6

3 2
1 2
1 3
1 3
2 1 2

3

提示

设 $k$ 为第二类查询的数量。

• （$3$ 分）：$n \le 16$，$q \le 16$；
• （$3$ 分）：$n \le 16$，$q \le 2 \cdot 10^5$；
• （$2$ 分）：$n \le 2000$，$q \le 2 \cdot 10^5$，$k \le 5$；
• （$8$ 分）：$n \le 2000$，$q \le 2000$；
• （$9$ 分）：$n \le 2 \cdot 10^5$，$q \le 2 \cdot 10^5$，$k \le 5$；
• （$30$ 分）：$n \le 2 \cdot 10^5$，$q \le 2 \cdot 10^5$，且第二类查询后不会出现第一类查询；
• （$45$ 分）：无额外限制。

翻译由 DeepSeek V3 完成