O - Notification Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020/12/27 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

あなたは、N 人のユーザが利用する SNS を運営しています。ユーザは 1 から N まで番号付けられていて、ユーザは他のユーザと双方向の友達関係を作ることができます。
今、この SNS には M 対の友達関係が成立しています。友達関係にも 1 から M までの番号がつけられており、i 番目の友達関係はユーザ a_i とユーザ b_i の間の関係です。

あなたの仕事は、この SNS に新たな機能を追加することです。
Q 個のクエリが与えられるので、順番に処理してください。 i 番目のクエリでは、整数 T_i, x_i が与えられます。クエリの内容は以下の通りです。

  • T_i = 1 のとき : ユーザ x_i と直接友達関係を持つユーザ全員 (ユーザ x_i は除く) に通知を 1 件送信する。これらの通知は最初未読の状態である。
  • T_i = 2 のとき : これまでにユーザ x_i に送信された通知のうち、未読のものの数を出力する。その後、それらの通知を既読にする。

制約

  • 入力は全て整数
  • 2 \le N \le 2 \times 10^5
  • 1 \le M \le 2 \times 10^5
  • 1 \le a_i \lt b_i \le N
  • i \neq j ならば (a_i, b_i) \neq (a_j, b_j)
  • 1 \le Q \le 2 \times 10^5
  • T_i \in \{1, 2\}
  • 1 \le x_i \le N

入力

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

N M
a_1 b_1
\vdots
a_M b_M
Q
T_1 x_1
\vdots
T_Q x_Q

出力

T_i = 2 のクエリごとに、答えを 1 行に出力せよ。

入力例 1

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

出力例 1

1
2
0

1 回目のクエリでは、ユーザ 1 の直接の友達である、ユーザ 2,3 に通知を 1 件送信します。各ユーザの未読通知の数は 0,1,1 になります。
2 回目のクエリでは、ユーザ 2 の未読通知の数である 1 を出力します。各ユーザの未読通知の数は 0,0,1 になります。
3 回目のクエリでは、ユーザ 1 の直接の友達である、ユーザ 2,3 に通知を 1 件送信します。各ユーザの未読通知の数は 0,1,2 になります。
4 回目のクエリでは、ユーザ 3 の未読通知の数である 2 を出力します。各ユーザの未読通知の数は 0,1,0 になります。
5 回目のクエリでは、ユーザ 1 の未読通知の数である 0 を出力します。各ユーザの未読通知の数は 0,1,0 になります。

入力例 2

7 7
1 4
1 6
3 4
3 5
3 7
4 5
4 7
15
1 1
2 3
1 4
2 2
1 5
1 1
1 4
2 4
2 3
2 1
1 7
1 2
2 5
2 4
2 2

出力例 2

0
0
3
3
2
2
1
0

入力例 3

10 13
1 2
1 5
1 9
2 3
2 4
3 5
3 6
3 9
4 8
5 7
5 10
6 7
6 10
20
1 5
2 8
1 4
2 9
1 1
1 6
2 8
1 10
2 7
1 10
1 10
2 8
1 7
2 5
1 9
2 2
1 9
1 4
2 4
2 6

出力例 3

0
0
1
2
0
5
2
0
4

Score : 6 points

Warning

Do not make any mention of this problem until December 27, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You run a social networking service used by N users. The users, numbered 1 through N, can make bidirectional friendships with other users.
There are now M friendships in the service, numbered 1 through M; Friendship i is between User a_i and User b_i.

Your task is to add new features to the service.
Process Q queries in the order they are given. The i-th query gives you integers T_i and x_i, which mean the following:

  • If T_i = 1: a notification is sent to each user (excluding User x_i) who is a direct friend of User x_i. These notifications are initially unread.
  • If T_i = 2: print the number of unread notifications sent to User x_i. Then, those notifications are marked as read.

Constraints

  • All values in input are integers.
  • 2 \le N \le 2 \times 10^5
  • 1 \le M \le 2 \times 10^5
  • 1 \le a_i \lt b_i \le N
  • If i \neq j, then (a_i, b_i) \neq (a_j, b_j).
  • 1 \le Q \le 2 \times 10^5
  • T_i \in \{1, 2\}
  • 1 \le x_i \le N

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
\vdots
a_M b_M
Q
T_1 x_1
\vdots
T_Q x_Q

Output

For each query with T_i = 2, print the response in its own line.

Sample Input 1

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

Sample Output 1

1
2
0

In the first query, a notification is sent to the direct friends of User 1 - User 2 and 3. Now, User 1, 2, 3 has 0, 1, 1 unread notification(s), respectively.
In the second query, we print the number of unread notifications sent to User 2, which is 1. Now, User 1, 2, and 3 has 0, 0, and 1 unread notification(s), respectively.
In the third query, a notification is sent to the direct friends of User 1 - User 2 and 3. Now, User 1, 2, 3 has 0, 1, 2 unread notification(s), respectively.
In the fourth query, we print the number of unread notifications sent to User 3, which is 2. Now, User 1, 2, 3 has 0, 1, 0 unread notification(s), respectively.
In the fifth query, we print the number of unread notifications sent to User 1, which is 0. Now, User 1, 2, 3 has 0, 1, 0 unread notification(s), respectively.

Sample Input 2

7 7
1 4
1 6
3 4
3 5
3 7
4 5
4 7
15
1 1
2 3
1 4
2 2
1 5
1 1
1 4
2 4
2 3
2 1
1 7
1 2
2 5
2 4
2 2

Sample Output 2

0
0
3
3
2
2
1
0

Sample Input 3

10 13
1 2
1 5
1 9
2 3
2 4
3 5
3 6
3 9
4 8
5 7
5 10
6 7
6 10
20
1 5
2 8
1 4
2 9
1 1
1 6
2 8
1 10
2 7
1 10
1 10
2 8
1 7
2 5
1 9
2 2
1 9
1 4
2 4
2 6

Sample Output 3

0
0
1
2
0
5
2
0
4