B - Investigation of Friend Relationships Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は、ある学校の生徒会長です。この学校には N 人の生徒がおり、それぞれ 1 から N までの出席番号が付けられています。

この学校では、生徒同士の間で「友達申請」を送ることができるシステムがあります。友達申請は一方向のものです。すなわち、生徒 u から生徒 v への友達申請と、生徒 v から生徒 u への友達申請は異なる申請として扱われ、一方のみが存在することも、両方が同時に存在することもありえます。

現在、M 件の友達申請が送られています。i 件目 (1 \leq i \leq M) の友達申請は、生徒 A_i から生徒 B_i へ送られたものです。

高橋君は、学校祭でペアを組んで活動するイベントを企画しています。このイベントでは、相互に友達申請を送り合っている生徒のペアだけが参加できます。ここで、生徒 u と生徒 v が「相互に友達申請を送り合っている」とは、生徒 u から生徒 v への友達申請と、生徒 v から生徒 u への友達申請の両方が存在する状態を指します。

高橋君のために、相互に友達申請を送り合っている生徒のペアの数を求めてください。ただし、生徒 u と生徒 v のペアと、生徒 v と生徒 u のペアは同じペアとして 1 つと数えます。

制約

  • 1 \leq N \leq 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N (1 \leq i \leq M)
  • A_i \neq B_i（自分自身への友達申請はない）
  • i \neq j ならば (A_i, B_i) \neq (A_j, B_j)（同じ生徒から同じ生徒への友達申請は高々 1 件である）
  • 入力はすべて整数である

入力

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

1 行目には、生徒の人数 N と友達申請の件数 M が、スペース区切りで与えられる。

続く M 行のうち i 番目の行 (1 \leq i \leq M) には、生徒 A_i から生徒 B_i への友達申請を表す整数の組 A_i, B_i がスペース区切りで与えられる。

出力

相互に友達申請を送り合っている生徒のペアの数を 1 行で出力してください。

入力例 1

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

出力例 1

2

入力例 2

3 6
1 2
2 1
2 3
3 2
1 3
3 1

出力例 2

3

入力例 3

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

出力例 3

5

Score : 266 pts

Problem Statement

Takahashi is the student council president of a school. There are N students in this school, each assigned a student number from 1 to N.

This school has a system where students can send "friend requests" to each other. Friend requests are one-directional. That is, a friend request from student u to student v and a friend request from student v to student u are treated as different requests — it is possible for only one of them to exist, or for both to exist simultaneously.

Currently, M friend requests have been sent. The i-th friend request (1 \leq i \leq M) was sent from student A_i to student B_i.

Takahashi is planning an event for the school festival where students participate in pairs. Only pairs of students who have mutually sent friend requests to each other can participate in this event. Here, students u and v "have mutually sent friend requests to each other" means that both a friend request from student u to student v and a friend request from student v to student u exist.

For Takahashi, find the number of pairs of students who have mutually sent friend requests to each other. Note that the pair of student u and student v and the pair of student v and student u are considered the same pair and counted as 1.

Constraints

  • 1 \leq N \leq 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N (1 \leq i \leq M)
  • A_i \neq B_i (no friend request to oneself)
  • If i \neq j, then (A_i, B_i) \neq (A_j, B_j) (there is at most one friend request from the same student to the same student)
  • All input values are integers

Input

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

The first line contains the number of students N and the number of friend requests M, separated by a space.

The i-th of the following M lines (1 \leq i \leq M) contains a pair of integers A_i, B_i separated by a space, representing a friend request from student A_i to student B_i.

Output

Print the number of pairs of students who have mutually sent friend requests to each other, in a single line.

Sample Input 1

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

Sample Output 1

2

Sample Input 2

3 6
1 2
2 1
2 3
3 2
1 3
3 1

Sample Output 2

3

Sample Input 3

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

Sample Output 3

5