题目描述

初始有 $n$ 个顶点，没有边。每条被加入的边上都写着一个整数 $c_i$。

对于同一个连通块内的两个顶点 $a$ 和 $b$，定义它们之间的简单路径为从 $a$ 到 $b$ 的最短路径。若一条简单路径上，每一种数值的出现次数都是偶数，则称这条路径是 好的。

你需要回答 $q$ 次询问，询问共有 $4$ 种类型：

• $1\ u\ v\ c$（$1 \le c \le 4 \cdot 10^9$）：加入一条连接顶点 $u$ 和 $v$、边权为 $c$ 的边；
• $2\ u\ v$：判断顶点 $u$ 和 $v$ 之间的简单路径是否是好的。如果它们之间不存在路径，输出 $-1$；
• $3\ u$：输出满足下列条件的点对 $(a,b)$ 的数量：$1 \le a < b \le n$，$a$ 和 $b$ 与 $u$ 属于同一个连通块，并且 $a$ 到 $b$ 的路径是好的；
• $4$：输出满足下列条件的点对 $(a,b)$ 的数量：$1 \le a < b \le n$，$a$ 到 $b$ 的路径是好的，并且 $a$ 到 $b$ 存在路径。

保证所有类型 $1$ 的询问中，加入的边都会连接两个不同的连通块。

输入格式

第一行包含两个整数 $n$（$1 \le n \le 2 \cdot 10^5$）和 $q$（$1 \le q \le 2 \cdot 10^5$），分别表示顶点数和询问数。

接下来 $q$ 行，每行包含一条询问的描述。每条询问的第一个整数 $t_i$ 表示询问类型。

• 若 $t_i=1$，后面跟着 $3$ 个整数 $u,v,c$（$1 \le u \ne v \le n$，$1 \le c \le 4 \cdot 10^9$）；
• 若 $t_i=2$，后面跟着 $2$ 个整数 $u,v$（$1 \le u,v \le n$）；
• 若 $t_i=3$，后面跟着 $1$ 个整数 $u$（$1 \le u \le n$）；
• 若 $t_i=4$，后面不再跟随其他整数。

输出格式

对于每个类型 $2$ 的询问，输出：

• -1：如果当前不存在对应的简单路径；
• YES：如果这条简单路径是 好的；
• NO：否则。

对于每个类型 $3$ 或类型 $4$ 的询问，输出一个整数，表示对应询问的答案。

你需要按照输入中询问出现的顺序依次回答。

输入 #1

5 11
1 1 2 1
2 1 3
1 2 3 1
3 2
2 1 2
1 2 4 2
1 2 5 2
3 3
2 4 5
2 1 4
4

输出 #1

-1
1
NO
2
YES
NO
2

子任务

1. （$5$ 分）对所有 $t_i=1$ 的询问，均有 $u_i=1$；
2. （$5$ 分）$n,q \le 20$；
3. （$7$ 分）$n,q \le 1000$；
4. （$3$ 分）$t_i \le t_{i+1}$，$t_i \le 2$，$c=1$；
5. （$6$ 分）$t_i \le t_{i+1}$，$t_i \le 2$，$c \le 8$；
6. （$11$ 分）$t_i \le t_{i+1}$，$t_i \le 2$；
7. （$9$ 分）$q=n$，对 $1 \le i < n$ 有 $t_i=1$，且 $t_q=4$；
8. （$17$ 分）存在一个整数 $e$，使得对所有 $1 \le i \le e$ 都有 $t_i=1$，并且对所有 $e<j\le q$ 都有 $t_j\ne 1$；
9. （$9$ 分）$c \le 1000$，图和测试数据随机生成。具体而言，对每个顶点 $v$（$2 \le v \le n$）随机选择 $p_v$（$1 \le p_v < v$），然后生成一个随机排列 $perm$，并令 $v=perm_v$，$p_v=perm_{p_v}$。询问类型随机选择（如果没有边可加，则不会选择第一类询问），询问中的所有值也随机选取；
10. （$28$ 分）无额外限制。