E - Pigeonhole Query Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 匹の鳩がおり、 1 から N までの番号がつけられています。また、 N 個の巣があり、 1 から N までの番号がつけられています。はじめ、鳩 i は巣 i にいます (1\leq i\leq N)。

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

  • 1 P H : 鳩 P を巣 H に移動させる。
  • 2 : 複数の鳩がいる巣の個数を出力する。

制約

  • 2\leq N\leq 10^6
  • 1\leq Q\leq 3\times 10^5
  • 1\leq P,H\leq N
  • 1 つ目の形式のクエリについて、鳩 P は移動する前に巣 H にいない
  • 入力は全て整数

入力

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

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

各クエリは以下の 2 種類のいずれかの形式で与えられる。

1 P H

2

出力

問題文の指示に従ってクエリへの答えを改行区切りで出力せよ。

入力例 1

4 7
2
1 1 2
2
1 3 2
2
1 3 4
2

出力例 1

0
1
1
2

初め、鳩 1,2,3,4 はそれぞれ巣 1,2,3,4 にいます。

  • 1 つ目のクエリについて、巣 1,2,3,4 にはそれぞれ 1,1,1,1 匹います。鳩が複数いる巣は存在しないので 0 を出力します。
  • 2 つ目のクエリについて、鳩 1 を巣 2 に移動します。
  • 3 つ目のクエリについて、巣 1,2,3,4 にはそれぞれ 0,2,1,1 匹います。鳩が複数いる巣は巣 2 の 1 つなので 1 を出力します。
  • 4 つ目のクエリについて、鳩 3 を巣 2 に移動します。
  • 5 つ目のクエリについて、巣 1,2,3,4 にはそれぞれ 0,3,0,1 匹います。鳩が複数いる巣は巣 2 の 1 つなので 1 を出力します。
  • 6 つ目のクエリについて、鳩 3 を巣 4 に移動します。
  • 7 つ目のクエリについて、巣 1,2,3,4 にはそれぞれ 0,2,0,2 匹います。鳩が複数いる巣は巣 2,4 の 2 つなので 2 を出力します。

入力例 2

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

出力例 2

0
1
2
1

Score : 300 points

Problem Statement

There are N pigeons numbered from 1 to N, and there are N nests numbered from 1 to N. Initially, pigeon i is in nest i for 1\leq i\leq N.

You are given Q queries, which you must process in order. There are two types of queries, each given in one of the following formats:

  • 1 P H : Move pigeon P to nest H.
  • 2 : Output the number of nests that contain more than one pigeon.

Constraints

  • 2 \leq N \leq 10^6
  • 1 \leq Q \leq 3\times 10^5
  • 1 \leq P, H \leq N
  • For a query of the first type, pigeon P is not in nest H before the move.
  • All input values are integers.

Input

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

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

Each query is given in one of the following two formats:

1 P H

2

Output

Print the answer to each query on a new line according to the instructions in the problem statement.

Sample Input 1

4 7
2
1 1 2
2
1 3 2
2
1 3 4
2

Sample Output 1

0
1
1
2

Initially, pigeons 1,2,3,4 are in nests 1,2,3,4, respectively.

  • For the 1st query, the counts of pigeons in nests 1,2,3,4 are 1,1,1,1. No nests contain multiple pigeons, output 0.
  • For the 2nd query, move pigeon 1 to nest 2.
  • For the 3rd query, the counts become 0,2,1,1, respectively. One nest (nest 2) contains multiple pigeons, so output 1.
  • For the 4th query, move pigeon 3 to nest 2.
  • For the 5th query, the counts become 0,3,0,1, respectively. One nest (nest 2) contains multiple pigeons, so output 1.
  • For the 6th query, move pigeon 3 to nest 4.
  • For the 7th query, the counts become 0,2,0,2, respectively. Two nests (nests 2 and 4) contain multiple pigeons, so output 2.

Sample Input 2

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

Sample Output 2

0
1
2
1