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