愚直にクエリを処理すると、時間計算量が \(O(NQ+M)\) になり TLE してしまいます。

そこで、以下のようにクエリを処理します。

• ユーザ \(X_i\) の友達が \(\sqrt M\) 人未満の場合、 \(T_i=1\) のクエリで愚直に通知を配る。
• ユーザ \(X_i\) の友達が \(\sqrt M\) 人以上の場合、 \(T_i=1\) のクエリでは通知を配らず、ユーザ \(X_i\) の友達に \(T_i=2\) のクエリが来た時に取りに来てもらう。
  • この処理のために、あらかじめユーザ \(x\) の友達のうち「友達が \(\sqrt M\) 人以上いるユーザ」のリストを作っておく。このリストの大きさは \(O(\sqrt M)\) である。

このようにすることで、時間計算量が \(O((M+Q)\sqrt M+N)\) になり、十分高速に処理することができます。

回答例 (Python)

N, M = map(int, input().split())
g = [list() for i in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    g[A].append(B)
    g[B].append(A)

rt = int(M ** 0.5)
g_high = [list(x for x in g[i] if len(g[x]) >= rt) for i in range(N)]
cnt_low = [0] * N
cnt_high = [0] * N
before = [0] * N

Q = int(input())
for _ in range(Q):
    T, X = map(int, input().split())
    X -= 1
    if T == 1:
        if len(g[X]) < rt:
            for at in g[X]:
                cnt_low[at] += 1
        else:
            cnt_high[X] += 1
    else:
        ans = cnt_low[X]
        for at in g_high[X]:
            ans += cnt_high[at]
        print(ans - before[X])
        before[X] = ans