XYZ Operations

View as PDF

Time limit: 1.0s , Memory limit: 256M , Points: 1

Cho đơn đồ thị vô hướng gồm n đỉnh và m cạnh, các đỉnh được đánh số từ 1 đến n. Bạn hãy xác định xem có thể thực hiện nhiều nhất bao nhiêu thao tác như sau:

  • Chọn 3 đỉnh x, yz thỏa mãn giữa xy có cạnh nối, giữa yz có cạnh nối nhưng giữa xz không có cạnh nối, tiến hành thêm cạnh nối giữa xz.

Input

  • Dòng đầu tiên chứa hai số nguyên nm (2 \le n \le 2 \times 10^5 ; 0 \le m \le 2 \times 10^5).
  • m dòng tiếp theo, mỗi dòng chứa hai số nguyên uv mô tả các cạnh nối (1 \le u<v \le n).
  • Dữ liệu đảm bảo giữa hai đỉnh uv có tối đa một cạnh nối.

Output

  • In ra số lần thực hiện thao tác nhiều nhất.

Examples

Sample Input 1
5 5
1 2
2 3
1 4
4 5
1 5
Sample Output 1
5
Sample Input 2
4 2
1 2
3 4
Sample Output 2
0

Notes

Trong ví dụ đầu tiên, có thể thực hiện tổng cộng 5 thao tác như sau:

  1. Chọn x=1, y=2z=3, thêm cạnh nối giữa hai đỉnh 13.
  2. Chọn x=4, y=1z=2, thêm cạnh nối giữa hai đỉnh 42.
  3. Chọn x=4, y=1z=3, thêm cạnh nối giữa hai đỉnh 43.
  4. Chọn x=5, y=1z=2, thêm cạnh nối giữa hai đỉnh 52.
  5. Chọn x=5, y=1z=3, thêm cạnh nối giữa hai đỉnh 53.

Comments