F - 種類数 α Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300300

問題文

NN 枚のコインがあります。ii 枚目のコインの片方の面には整数 AiA_i、もう片方の面には整数 BiB_i が書かれています。

書かれている整数の組が同じであるコインを区別しないとき、コインは全部で何種類あるでしょうか?

制約

入力は以下の条件を満たす。

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 1Ai,Bi1091 \leq A_i,B_i \leq 10^9
  • 入力される値は全て整数

入力

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

NN
A1A_1 B1B_1
A2A_2 B2B_2
::
ANA_N BNB_N

出力

コインの種類数を出力せよ。


入力例 1Copy

Copy
5
1 2
2 1
3 4
5 5
3 4

出力例 1Copy

Copy
3

書かれた整数の組が (1,2), (3,4), (5,5)(1,2),\ (3,4),\ (5,5) である 33 種類のコインがあります。

11 枚目のコインと 22 枚目のコインはひっくり返すと同じ種類のコインであることに注意してください。



2025-04-06 (Sun)
08:25:08 +00:00