FF

题目描述

Takahashi 经营着一个名为 “Twidai” 的社交网络服务，拥有从用户 $1$ 到用户 $N$ 的 $N$ 名用户。 在 Twidai 中，用户可以关注或取关其他用户。 自 Twidai 启动以来已经进行了 $Q$ 次操作。 第 $i$ 次 $(1\leq i\leq Q)$ 操作由三个整数 $T_i$、$A_i$ 和 $B_i$ 表示，其含义如下：

如果 $T_i = 1$：表示用户 $A_i$ 关注用户 $B_i$。如果在该操作发生时用户 $A_i$ 已经关注用户 $B_i$，则不发生任何变化。 如果 $T_i = 2$：表示用户 $A_i$ 取关用户 $B_i$。如果在该操作发生时用户 $A_i$ 并未关注用户 $B_i$，则不发生任何变化。 如果 $T_i = 3$：表示询问用户 $A_i$ 和 $B_i$ 是否相互关注。如果用户 $A_i$ 正在关注用户 $B_i$ 且用户 $B_i$ 正在关注用户 $A_i$，则需要输出 $Yes$，否则输出 $No$。

服务启动时，没有任何用户关注任何用户。 按 $i$ 的升序输出所有满足 $T_i = 3$ 的操作的正确答案。

输入格式

输入从标准输入按如下格式给出： $N$ $Q$ $T _ 1$ $A _ 1$ $B _ 1$ $T _ 2$ $A _ 2$ $B _ 2$ $\vdots$ $T _ Q$ $A _ Q$ $B _ Q$

输出格式

输出 $X$ 行，其中 $X$ 是满足 $T _ i=3$ 的 $i$ 的个数 $(1\leq i\leq Q)$。 第 $j$ 行 $(1\leq j\leq X)$ 应当包含对第 $j$ 个满足 $T _ i=3$ 的操作的答案。

3 9
1 1 2
3 1 2
1 2 1
3 1 2
1 2 3
1 3 2
3 1 3
2 1 2
3 1 2

No
Yes
No
No

2 8
1 1 2
1 2 1
3 1 2
1 1 2
1 1 2
1 1 2
2 1 2
3 1 2

Yes
No

10 30
3 1 6
3 5 4
1 6 1
3 1 7
3 8 4
1 1 6
2 4 3
1 6 5
1 5 6
1 1 8
1 8 1
2 3 10
1 7 6
3 5 6
1 6 7
3 6 7
1 9 5
3 8 6
3 3 8
2 6 9
1 7 1
3 10 8
2 9 2
1 10 9
2 6 10
2 6 8
3 1 6
3 1 8
2 8 5
1 9 10

No
No
No
No
Yes
Yes
No
No
No
Yes
Yes

提示

$2 \leq N \leq 10 ^ 9$ $1 \leq Q \leq 2\times10 ^ 5$ $T _ i=1,2,3\ (1\leq i\leq Q)$ $1 \leq A _ i \leq N\ (1\leq i\leq Q)$ $1 \leq B _ i \leq N\ (1\leq i\leq Q)$ $A _ i\neq B _ i\ (1\leq i\leq Q)$ 存在 $i\ (1\leq i\leq Q)$ 使得 $T _ i=3$。 输入中的所有数值均为整数。Twidai 有三名用户。 这九个操作如下所示。

用户 $1$ 关注用户 $2$。此时没有其他用户有任何关注关系。 判断用户 $1$ 和 $2$ 是否相互关注。用户 $1$ 正在关注用户 $2$，但用户 $2$ 并未关注用户 $1$，因此该操作的正确答案为 $No$。 用户 $2$ 关注用户 $1$。 判断用户 $1$ 和 $2$ 是否相互关注。用户 $1$ 正在关注用户 $2$，且用户 $2$ 正在关注用户 $1$，因此该操作的正确答案为 $Yes$。 用户 $2$ 关注用户 $3$。 用户 $3$ 关注用户 $2$。 判断用户 $1$ 和 $3$ 是否相互关注。用户 $1$ 并未关注用户 $3$，且用户 $3$ 也并未关注用户 $1$，因此该操作的正确答案为 $No$。 用户 $1$ 取关用户 $2$。 判断用户 $1$ 和 $2$ 是否相互关注。用户 $2$ 正在关注用户 $1$，但用户 $1$ 并未关注用户 $2$，因此该操作的正确答案为 $No$。
同一用户可能会多次关注同一名用户。

标签: AtCoder|abc278C

来源

AtCoder|abc278C