問題一覧 > 通常問題

No.3390 Public or Private

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 57
作問者 : yu23578 / テスター : GaLLium yt142857 aa36 Germanium32
お気に入りにしたユーザー ProblemId : 12762 / 自分の提出
問題文最終更新日: 2026-10-22 23:53:26
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 490 (順位表) の他の問題:

Problem Statement

The social network "Y23", run by yu23578, currently has $N$ users, numbered from user $1$ to user $N$.

Each user of "Y23" has a status of either Public or Private, and currently the status of every user is Public.

"Y23" also has a "follow" feature. There are currently $M$ follow relationships: user $u_i$ follows user $v_i$.

Process $Q$ operations and answer the associated questions in order. For the $i$-th operation, $q_i,\ a_i,\ b_i$ are given.

When $q_i=1$, user $a_i$ acts as follows with respect to user $b_i$:
  • If already following, unfollow user $b_i$.
  • If not following, follow user $b_i$.
When $q_i=2$, depending on the status of user $a_i$:
  • If it is Public, change the status of user $a_i$ to Private.
  • If it is Private, change the status of user $a_i$ to Public.
After the operation, print the number of users other than $a_i$ who satisfy at least one of the following: "is followed by user $a_i$" or "has status Public".

Constraints

  • $2 \le N \le 10^9$
  • $1 \le M \le \mathrm{min} (N(N-1) , 2 \times 10^5)$
  • $1 \le u_i,v_i \le N$
  • $u_i \neq v_i$
  • If $i \neq j$, then $(u_i,v_i) \neq (u_j,v_j)$
  • $1 \le Q \le 3000$
  • When $q_i=1$, $1 \le a_i,b_i \le N$
  • When $q_i=2$, $1 \le a_i \le N,\ b_i = -1$
  • $a_i \neq b_i$
  • All input values are integers

Input

$N\ M$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_M\ v_M$
$Q$
$q_1\ a_1\ b_1$
$q_2\ a_2\ b_2$
$\vdots$
$q_Q\ a_Q\ b_Q$

Output

Print a newline at the end.

Sample

Sample 1
Input
5 2
1 2
1 3
6
1 2 1
2 1 -1
2 4 -1
1 3 4
1 2 1
2 1 -1
Output
4
4
3
3
2
3

Explanation (collapsed because it is long) Initially, the follow relationships among the users are as follows.



In query $1$, user $2$ follows user $1$.
The $4$ users $1,3,4,5$ satisfy the condition in the problem statement.



In query $2$, the status of user $1$ becomes Private.
The $4$ users $2,3,4,5$ satisfy the condition in the problem statement.



In query $3$, the status of user $4$ becomes Private.
The $3$ users $2,3,5$ satisfy the condition in the problem statement.



In query $4$, user $3$ follows user $4$.
The $3$ users $2,4,5$ satisfy the condition in the problem statement.



In query $5$, user $2$ unfollows user $1$.
The $2$ users $3,5$ satisfy the condition in the problem statement.



In query $6$, the status of user $1$ becomes Public.
The $3$ users $2,3,5$ satisfy the condition in the problem statement.

Sample 2
Input
2 1
1 2
2
2 1 -1
2 2 -1
Output
1
0

There may be no users satisfying the condition.

Sample 3
Input
1000000000 9
1 2
12 23
123 235
1234 2357
12345 23578
2345 3578
345 578
45 78
5 8
10
1 3 5
1 89 34
1 314 159
1 44 23
1 1 2
2 1 -1
2 23 -1
2 2357 -1
2 1 -1
2 23578 -1
Output
999999999
999999999
999999999
999999999
999999999
999999999
999999998
999999997
999999997
999999997

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。