F - 三角関係 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

問題文

N 人の人がいます。

人 i の親友は人 A_i です。人 i が人 j の親友ならば、人 j は人 i の親友であることが保証されます。

人 i が好きな人は人 B_i です。

次の条件を全て満たす整数の組 (i,j,k) の個数を求めてください。

  • 1 \leq i < j \leq N
  • 1 \leq k \leq N
  • 人 i と人 j は親友である
  • 人 i と人 j はともに人 k が好きな人である

制約

  • 2 \leq N \leq 2\times 10^5
  • N は偶数
  • 1 \leq A_i,B_i \leq N
  • A_i \neq i
  • A_i=j ならば A_j=i
  • B_i \neq i
  • 入力は全て整数である

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

答えを出力せよ。

入力例 1

6
6 3
3 1
2 1
5 5
4 4
1 2

出力例 1

1

(2,3,1) のみが条件を満たします。

入力例 2

10
9 7
3 10
2 8
5 8
4 8
10 10
8 5
7 7
1 7
6 8

出力例 2

2

(1,9,7),(4,5,8) が条件を満たします。

Problem Statement

There are N people.

Person i's best friend is person A_i. If person i is person j's best friend, then it is also guaranteed that person j is person i's best friend.

Person i loves person B_i.

Find the number of triples of integers (i,j,k) such that:

  • 1 \leq i < j \leq N.
  • 1 \leq k \leq N.
  • Persons i and j are best friends of each other.
  • Persons i and j both love person k.

Constraints

  • 2 \leq N \leq 2\times 10^5
  • N is even.
  • 1 \leq A_i,B_i \leq N
  • A_i \neq i
  • If A_i=j, then A_j=i.
  • B_i \neq i
  • 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

Print the answer.

Sample Input 1

6
6 3
3 1
2 1
5 5
4 4
1 2

Sample Output 1

1

Only (2,3,1) is eligible.

Sample Input 2

10
9 7
3 10
2 8
5 8
4 8
10 10
8 5
7 7
1 7
6 8

Sample Output 2

2

Tuples (1,9,7),(4,5,8) are eligible.