D - New Friends Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 350 点

問題文

1 から N の番号がついた N 人のユーザが利用している SNS があります。

この SNS では 2 人のユーザが互いに友達になれる機能があります。
友達関係は双方向的です。すなわち、ユーザ X がユーザ Y の友達であるならば、必ずユーザ Y はユーザ X の友達です。

現在 SNS 上には M 組の友達関係が存在し、i 組目の友達関係はユーザ A_i とユーザ B_i からなります。

以下の操作を行える最大の回数を求めてください。

  • 操作：3 人のユーザ X, Y, Z であって、X と Y は友達、Y と Z は友達であり、X と Z は友達でないようなものを選ぶ。X と Z を友達にする。

制約

  • 2 \leq N \leq 2\times 10^5
  • 0 \leq M \leq 2\times 10^5
  • 1\leq A_i < B_i \leq N
  • (A_i,B_i) は相異なる
  • 入力は全て整数である

入力

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

N M
A_1 B_1
\vdots
A_M B_M

出力

答えを出力せよ。

入力例 1

4 3
1 2
2 3
1 4

出力例 1

3

次のようにして「友達の友達と新たに友達になる」という操作は 3 回行えます。

  • ユーザ 1 が友達(ユーザ 2)の友達であるユーザ 3 と新たに友達になる
  • ユーザ 3 が友達(ユーザ 1)の友達であるユーザ 4 と新たに友達になる
  • ユーザ 2 が友達(ユーザ 1)の友達であるユーザ 4 と新たに友達になる

4 回以上行うことはできません。

入力例 2

3 0

出力例 2

0

もともと友達関係が存在しないとき、新たな友達関係は発生しません。

入力例 3

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

出力例 3

12

Score: 350 points

Problem Statement

There is an SNS used by N users, labeled with numbers from 1 to N.

In this SNS, two users can become friends with each other.
Friendship is bidirectional; if user X is a friend of user Y, user Y is always a friend of user X.

Currently, there are M pairs of friendships on the SNS, with the i-th pair consisting of users A_i and B_i.

Determine the maximum number of times the following operation can be performed:

  • Operation: Choose three users X, Y, and Z such that X and Y are friends, Y and Z are friends, but X and Z are not. Make X and Z friends.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq A_i < B_i \leq N
  • The pairs (A_i, B_i) are distinct.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

4 3
1 2
2 3
1 4

Sample Output 1

3

Three new friendships with a friend's friend can occur as follows:

  • User 1 becomes friends with user 3, who is a friend of their friend (user 2)
  • User 3 becomes friends with user 4, who is a friend of their friend (user 1)
  • User 2 becomes friends with user 4, who is a friend of their friend (user 1)

There will not be four or more new friendships.

Sample Input 2

3 0

Sample Output 2

0

If there are no initial friendships, no new friendships can occur.

Sample Input 3

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

Sample Output 3

12