← 返回题目列表

AtCoder · past23_f

F. 三角恋

中文机器翻译题面 查看原题

问题陈述

有 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
  • If 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) 符合资格。