Problem Description

You are operating an SNS with $ N $ users, numbered from $ 1 $ to $ N $. Users can form bidirectional friendship relationships with other users. Currently, there are $ M $ pairs of friendship relationships established in this SNS. Each friendship relationship is numbered from $ 1 $ to $ M $, and the $ i $-th friendship relationship is between users $ a_i $ and $ b_i $.

Your task is to add a new feature to this SNS. You will be given $ Q $ queries to process in order. In the $ i $-th query, you will be given integers $ T_i $ and $ x_i $. The content of the queries is as follows:

• When $ T_i = 1 $: Send one notification to all users who are directly friends with user $ x_i $ (excluding user $ x_i $). These notifications are initially unread.
• When $ T_i = 2 $: Output the number of unread notifications that have been sent to user $ x_i $. Then, mark those notifications as read.

Input Format

The input is given from the 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 Format

For each query where $ T_i = 2 $, output the answer on a single line.

Sample Input and Output

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

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

Notes/Hints

Constraints

• All input values are integers.
• $2 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le a_i < 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$

Sample Explanation 1

In the first query, send one notification to users $ 2 $ and $ 3 $, who are direct friends of user $ 1 $. The number of unread notifications for each user becomes $ 0, 1, 1 $. In the second query, output the number of unread notifications for user $ 2 $, which is $ 1 $. The number of unread notifications for each user becomes $ 0, 0, 1 $. In the third query, send one notification to users $ 2 $ and $ 3 $, who are direct friends of user $ 1 $. The number of unread notifications for each user becomes $ 0, 1, 2 $. In the fourth query, output the number of unread notifications for user $ 3 $, which is $ 2 $. The number of unread notifications for each user becomes $ 0, 1, 0 $. In the fifth query, output the number of unread notifications for user $ 1 $, which is $ 0 $. The number of unread notifications for each user remains $ 0, 1, 0 $.

见题面 Input 部分

见题面 Output 部分