AT_past202112_g 連結
题目描述
有一个有 $N$ 个顶点的无向图,最初 $2$ 个顶点中没有一个被边连接。
给定 $Q$ 次查询,应按给定的顺序处理。
查询可以是以下 $2$ 种类型:
- `1 u v`:如果没有直接连接顶点 $u$ 和顶点 $v$ 的边,那么就在它们之间添加一条无向边。如果有直接连接顶点 $u$ 和顶点 $v$ 的边,则删除直接连接顶点 $u$ 和顶点 $v$ 的边。
- `2 u v`:如果可能通过沿着边从顶点 $u$ 到顶点 $v$,则输出 `Yes`,否则输出 `No`。
输入格式
输入通过标准输入,格式如下。
第一行两个整数,$N$ 和 $Q$。
第 $2$ 行至 $Q+1$ 行,分别为 $Q$ 次询问。
第 $2$ 行至第 $Q+1$ 行中的每次查询都以下列形式之一给出:
> $1$ $u$ $v$
> $2$ $u$ $v$
输出格式
按照给出的顺序输出第 $2$ 类查询的答案,每次查询的答案之间用换行符隔开。
说明/提示
### 制約
- $ 2\ \leq\ N\ \leq\ 100 $
- $ 1\ \leq\ Q\ \leq\ 10000 $
- $ 1\ \leq\ u,v\ \leq\ N $
- $ u\ \neq\ v $
- $ 2 $ 種類目のクエリが $ 1 $ 回以上与えられる。
- 入力は全て整数である。
### Sample Explanation 1
\- $ 1 $ 個目のクエリの直前の時点で、頂点 $ 1 $ と頂点 $ 2 $ は辺で結ばれていないため、辺を追加します。 - $ 2 $ 個目のクエリの直前の時点で、頂点 $ 3 $ と頂点 $ 2 $ は辺で結ばれていないため、辺を追加します。 - $ 3 $ 個目のクエリの時点で、$ 1 $ , $ 2 $ 個目のクエリで追加された辺を辿って、頂点 $ 1 $ $ \to $ 頂点 $ 2 $ $ \to $ 頂点 $ 3 $ と移動できるため、`Yes` を出力します。 - $ 4 $ 個目のクエリの直前の時点で、頂点 $ 2 $ と頂点 $ 3 $ を直接結ぶ辺は存在するため、これを削除します。 - $ 5 $ 個目のクエリの時点では、頂点 $ 1 $ と頂点 $ 2 $ を結ぶ辺しか存在せず、頂点 $ 1 $ から頂点 $ 3 $ へは辿り着けないため、 `No` を出力します。