C - FF Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

高橋君が運営する SNS「Twidai」にはユーザー 1 からユーザー N までの N 人のユーザーがいます。 Twidai では、ユーザーは別のユーザーをフォローすることや、フォローを解除することができます。

Twidai がサービスを開始してから、Q 回の操作が行われました。 i 回目 (1\leq i\leq Q) の操作は 3 つの整数 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 と答える必要がある。

サービス開始時には、どのユーザーも他のユーザーをフォローしていません。

すべての T _ i=3 であるような操作に対して、i が小さいほうから順番に正しい答えを出力してください。

制約

  • 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)
  • T _ i=3 となる i\ (1\leq i\leq Q) が存在する
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
T _ 1 A _ 1 B _ 1
T _ 2 A _ 2 B _ 2
\vdots
T _ Q A _ Q B _ Q

出力

T _ i=3 であるような i\ (1\leq i\leq Q) の個数を X として、X 行出力せよ。 j\ (1\leq j\leq X) 行目には j 番目の T _ i=3 であるような操作に対する答えを出力せよ。

入力例 1

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

出力例 1

No
Yes
No
No

Twidai には 3 人のユーザーがいます。 9 回の操作はそれぞれ次のようになっています。

  • ユーザー 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 です。

入力例 2

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

出力例 2

Yes
No

同じユーザーに対して何度もフォロー操作をする場合があります。

入力例 3

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

出力例 3

No
No
No
No
Yes
Yes
No
No
No
Yes
Yes

Score : 300 points

Problem Statement

Takahashi runs an SNS "Twidai," which has N users from user 1 through user N. In Twidai, users can follow or unfollow other users.

Q operations have been performed since Twidai was launched. The i-th (1\leq i\leq Q) operation is represented by three integers T_i, A_i, and B_i, whose meanings are as follows:

  • If T_i = 1: it means that user A_i follows user B_i. If user A_i is already following user B_i at the time of this operation, it does not make any change.
  • If T_i = 2: it means that user A_i unfollows user B_i. If user A_i is not following user B_i at the time of this operation, it does not make any change.
  • If T_i = 3: it means that you are asked to determine if users A_i and B_i are following each other. You need to print Yes if user A_i is following user B_i and user B_i is following user A_i, and No otherwise.

When the service was launched, no users were following any users.

Print the correct answers for all operations such that T_i = 3 in ascending order of i.

Constraints

  • 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)
  • There exists i\ (1\leq i\leq Q) such that T _ i=3.
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N Q
T _ 1 A _ 1 B _ 1
T _ 2 A _ 2 B _ 2
\vdots
T _ Q A _ Q B _ Q

Output

Print X lines, where X is the number of i's (1\leq i\leq Q) such that T _ i=3. The j-th (1\leq j\leq X) line should contain the answer to the j-th operation such that T _ i=3.

Sample Input 1

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

Sample Output 1

No
Yes
No
No

Twidai has three users. The nine operations are as follows.

  • User 1 follows user 2. No other users are following or followed by any users.
  • Determine if users 1 and 2 are following each other. User 1 is following user 2, but user 2 is not following user 1, so No is the correct answer to this operation.
  • User 2 follows user 1.
  • Determine if users 1 and 2 are following each other. User 1 is following user 2, and user 2 is following user 1, so Yes is the correct answer to this operation.
  • User 2 follows user 3.
  • User 3 follows user 2.
  • Determine if users 1 and 3 are following each other. User 1 is not following user 3, and user 3 is not following user 1, so No is the correct answer to this operation.
  • User 1 unfollows user 2.
  • Determine if users 1 and 2 are following each other. User 2 is following user 1, but user 1 is not following user 2, so No is the correct answer to this operation.

Sample Input 2

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

Sample Output 2

Yes
No

A user may follow the same user multiple times.

Sample Input 3

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

Sample Output 3

No
No
No
No
Yes
Yes
No
No
No
Yes
Yes