/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君はゲームをしています。このゲームには 1 から N の番号がついた N 個のスキルがあります。
N 個の整数の組 (A_1,B_1), \dots,(A_N,B_N) が与えられます。
(A_i,B_i)=(0,0) のとき高橋君はスキル i を習得済みです。
そうでないとき、スキル A_i,B_i の少なくとも一方を習得済みのときかつそのときに限りスキル i を習得することができます。
既に取得済みのスキルも含め、高橋君が最終的に習得することができるスキルの個数を求めてください。
制約
- 1\leq N \leq 2\times 10^5
- (A_i,B_i)=(0,0) または 1\leq A_i,B_i \leq N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
答えを出力せよ。
入力例 1
6 0 0 1 3 3 2 5 5 4 6 6 4
出力例 1
3
最初、高橋君はスキル 1 を習得済みです。スキル 1 を習得済みのためスキル 2 を習得することができ、スキル 2 を習得したことでスキル 3 を習得できます。
スキル 4,5,6 を習得することはできないため、答えは 3 となります。
入力例 2
4 0 0 0 0 0 0 0 0
出力例 2
4
Score : 300 points
Problem Statement
Takahashi is playing a game. This game has N skills numbered 1 through N.
You are given N pairs of integers (A_1,B_1), \dots,(A_N,B_N).
If (A_i,B_i)=(0,0), then Takahashi has already learned skill i.
Otherwise, Takahashi can learn skill i if and only if at least one of skills A_i and B_i has already been learned.
Including the skills already learned, find the number of skills that Takahashi can ultimately learn.
Constraints
- 1\leq N \leq 2\times 10^5
- (A_i,B_i)=(0,0) or 1\leq A_i,B_i \leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Output the answer.
Sample Input 1
6 0 0 1 3 3 2 5 5 4 6 6 4
Sample Output 1
3
At first, Takahashi has already learned skill 1. Because skill 1 has been learned, skill 2 can be learned, and learning skill 2 enables learning skill 3. Since it is impossible to learn skills 4,5,6, the answer is 3.
Sample Input 2
4 0 0 0 0 0 0 0 0
Sample Output 2
4