Bạn là một điệp viên hoạt động phía sau những sự kiện lịch sử, ngày ngày nỗ lực vì hòa bình thế giới. Thế giới này có \(N\) quốc gia, được đánh số khác nhau từ \(1\) đến \(N\). Mục tiêu của bạn là giúp các quốc gia này xây dựng quan hệ hữu nghị với nhau nhiều nhất có thể. Để lên kế hoạch cho công việc, bạn đã vẽ một sơ đồ thể hiện quan hệ quốc tế hiện tại.

Bạn chuẩn bị một tờ giấy vẽ lớn và trước tiên đánh dấu \(N\) điểm, mỗi điểm biểu thị một quốc gia. Tiếp theo, để thể hiện quan hệ quốc tế hiện tại, bạn vẽ \(M\) mũi tên nối các cặp quốc gia. Mũi tên từ điểm biểu thị quốc gia \(a\) đến điểm biểu thị một quốc gia khác \(b\) có nghĩa là “hiện tại, quốc gia \(a\) đang cử đại sứ đến quốc gia \(b\)”. Từ đây, ta gọi mũi tên từ điểm biểu thị quốc gia \(a\) đến điểm biểu thị quốc gia \(b\) là mũi tên \((a, b)\). Như vậy, \(N\) điểm và \(M\) mũi tên vừa vẽ tạo thành sơ đồ quan hệ quốc tế hiện tại.

Để tạo cơ hội xây dựng quan hệ hữu nghị giữa các quốc gia, ta cân nhắc tổ chức hội nghị ký kết hiệp ước hữu nghị giữa hai quốc gia, sau đây gọi ngắn gọn là “hội nghị”. Để hai quốc gia \(p, q\) có thể tổ chức hội nghị, cần có một quốc gia \(x\) làm trung gian và đang cử đại sứ đến cả hai quốc gia đó. Sau hội nghị, mỗi quốc gia sẽ cử đại sứ đến quốc gia còn lại. Nói cách khác, để quốc gia \(p\) và quốc gia \(q\) tổ chức hội nghị, phải tồn tại quốc gia \(x\) sao cho có cả hai mũi tên \((x, p)\) và \((x, q)\). Sau hội nghị, ta vẽ thêm hai mũi tên \((p, q)\) và \((q, p)\). Tuy nhiên, nếu một mũi tên đã có sẵn thì không vẽ thêm mũi tên đó.

Công việc của bạn là chọn hai quốc gia có thể tổ chức hội nghị cùng với quốc gia làm trung gian, rồi cho họ tổ chức hội nghị. Khi mô phỏng công việc này bằng sơ đồ, bạn quyết định dùng số mũi tên trên giấy làm thước đo mức độ thế giới tiến gần đến hòa bình. Cụ thể, bạn muốn biết số mũi tên lớn nhất có thể có trên giấy sau khi lặp lại thao tác chọn hai quốc gia và cho họ tổ chức hội nghị.

Yêu cầu

Cho số quốc gia trên thế giới và thông tin về quan hệ quốc tế hiện tại. Hãy viết chương trình tìm số mũi tên lớn nhất có thể có trên giấy bằng cách lặp lại thao tác chọn hai quốc gia và cho họ tổ chức hội nghị.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên \(N, M\), cách nhau bởi dấu cách. \(N\) là số điểm trên giấy, cũng là số quốc gia trên thế giới; \(M\) là số mũi tên trên giấy.
• \(M\) dòng tiếp theo mô tả các mũi tên trên giấy. Dòng thứ \(i\) trong số này (\(1 \le i \le M\)) chứa hai số nguyên \(A_i, B_i\), cách nhau bởi dấu cách. Điều này có nghĩa là trên giấy có một mũi tên từ điểm biểu thị quốc gia \(A_i\) đến điểm biểu thị quốc gia \(B_i\), tức là quốc gia \(A_i\) đang cử đại sứ đến quốc gia \(B_i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số mũi tên lớn nhất có thể đạt được. Lưu ý rằng số này bao gồm cả các mũi tên đã có ban đầu và các mũi tên được vẽ thêm nhờ các hội nghị.

Ràng buộc

Tất cả dữ liệu đầu vào thỏa mãn:

• \(1 \le N \le 100\,000\).
• \(0 \le M \le 200\,000\).
• \(1 \le A_i \le N \quad (1 \le i \le M)\).
• \(1 \le B_i \le N \quad (1 \le i \le M)\).
• \(A_i \ne B_i \quad (1 \le i \le M)\).
• \((A_i, B_i) \ne (A_j, B_j) \quad (1 \le i < j \le M)\).

Phân nhóm

• Nhóm 1 (5 điểm): \(N \le 100\)
• Nhóm 2 (30 điểm): \(N \le 5\,000\)
• Nhóm 3 (65 điểm): Không có ràng buộc bổ sung.

Ví dụ

5 4
1 2
1 3
4 3
4 5

10