C - 403 Forbidden Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

WAtCoder には N 人のユーザーがおり、1 から N までの番号がつけられています。 また、M 個のコンテストページがあり、1 から M までの番号がつけられています。 はじめ、すべてのユーザはどのコンテストページの閲覧権限も持っていません。

Q 個のクエリが与えられるので、順に処理してください。クエリは 3 種類あり、以下のいずれかの形式で与えられます。

  • 1 X Y: ユーザ X にコンテストページ Y の閲覧権限を付与する。
  • 2 X: ユーザ X にすべてのコンテストページの閲覧権限を付与する。
  • 3 X Y: ユーザ X がコンテストページ Y を閲覧できるかを答える。

クエリの中で、あるユーザがすでに閲覧権限を持っているコンテストページについて、重ねて閲覧権限を付与されることもあります。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq X \leq N
  • 1 \leq Y \leq M
  • 入力はすべて整数

入力

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

N M Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリ \mathrm{query}_i は以下の 3 種類のいずれかの形式で与えられる。

1 X Y

2 X

3 X Y

出力

3 種類目のクエリのそれぞれについて、ユーザ X がコンテストページ Y を閲覧できるならば Yes を、そうでなければ No を改行区切りで出力せよ。

入力例 1

2 3 5
1 1 2
3 1 1
3 1 2
2 2
3 2 3

出力例 1

No
Yes
Yes
  • 1 つ目のクエリで、ユーザ 1 にコンテストページ 2 の閲覧権限を付与します。
  • 2 つ目のクエリの時点で、ユーザ 1 が閲覧できるコンテストページは 2 のみです。コンテストページ 1 の閲覧権限を持っていないので、No を出力します。
  • 3 つ目のクエリの時点で、ユーザ 1 はコンテストページ 2 の閲覧権限を持っているので、Yes を出力します。
  • 4 つ目のクエリで、ユーザ 2 にすべてのコンテストページの閲覧権限を付与します。
  • 5 つ目のクエリの時点で、ユーザ 2 が閲覧できるコンテストページは 1,2,3 です。コンテストページ 3 の閲覧権限を持っているので、Yes を出力します。

入力例 2

5 5 10
2 2
3 4 4
1 1 1
1 4 1
1 4 2
1 4 4
1 2 4
3 3 2
3 5 4
3 2 1

出力例 2

No
No
No
Yes

Score : 300 points

Problem Statement

There are N users on WAtCoder, numbered from 1 to N, and M contest pages, numbered from 1 to M. Initially, no user has view permission for any contest page.

You are given Q queries to process in order. Each query is of one of the following three types:

  • 1 X Y: Grant user X view permission for contest page Y.
  • 2 X: Grant user X view permission for all contest pages.
  • 3 X Y: Answer whether user X can view contest page Y.

It is possible for a user to be granted permission for the same contest page multiple times.

Constraints

  • 1 \le N \le 2\times 10^5
  • 1 \le M \le 2\times 10^5
  • 1 \le Q \le 2\times 10^5
  • 1 \le X \le N
  • 1 \le Y \le M
  • All input values are integers.

Input

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

N M Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each \mathrm{query}_i is in one of the following formats:

1 X Y

2 X

3 X Y

Output

For each query of the third type, print Yes if user X can view contest page Y, otherwise print No, each on its own line.

Sample Input 1

2 3 5
1 1 2
3 1 1
3 1 2
2 2
3 2 3

Sample Output 1

No
Yes
Yes
  • In the first query, user 1 is granted permission to view contest page 2.
  • At the second query, user 1 can view only page 2; they cannot view page 1, so print No.
  • At the third query, user 1 can view page 2, so print Yes.
  • In the fourth query, user 2 is granted permission to view all pages.
  • At the fifth query, user 2 can view pages 1,2,3; they can view page 3, so print Yes.

Sample Input 2

5 5 10
2 2
3 4 4
1 1 1
1 4 1
1 4 2
1 4 4
1 2 4
3 3 2
3 5 4
3 2 1

Sample Output 2

No
No
No
Yes