Giá trị lớn nhất của đồ thị (valg.*)

Cho đồ thị \(G\) có \(n\) đỉnh, các đỉnh được đánh số từ 1 đến \(n\). Ban đầu đồ thị không có cạnh nào. Cho một danh sách \(X\) gồm \(m\) cạnh, cạnh \(\left( u_{i},\ v_{i} \right)\ \forall\ i \in \lbrack 1,m\rbrack\) nối đỉnh \(u_{i}\) với \(v_{i}\). Bạn hãy chọn các cạnh trong danh sách \(X\) để thêm vào đồ thị \(G\) theo một thứ tự nhất định sao cho sao cho giá trị của đồ thị là lớn nhất. Giá trị của đồ thị được tính theo quy tắc:

1. Gọi giá trị của đồ thị \(G\) là \(valG\), lúc đầu chưa có cạnh nào được đưa vào đồ thị thì \(valG = 0\)

2. Khi thêm một cạnh \((u,v)\) vào đồ thị thì số lượng đỉnh đến được từ \(u\) và số lượng đỉnh đến được từ \(v\) trong đồ thị được cộng vào \(valG\). Một đỉnh \(x\) được gọi là đến được từ đỉnh \(y\) nếu có đường đi từ \(x\) đến \(y\).

Ví dụ: cho đồ thị có \(n = 5\) và danh sách \(X\ \)có \(m = 4\) cạnh \((1,\ 2);(3,\ 4);(4,5);(5,3)\ \)

• Nếu thêm lần lượt các cạnh theo đúng thứ tự trong danh sách \(X\) thì giá trị của đồ thị:

Đồ thị ban đầu		\[valG = 0\]
Thêm cạnh \((1,2)\)		\[valG + = 1 + 1 + 0 + 0 + 0\] \[\rightarrow valG = 2\]
Thêm cạnh \((3,4)\)		\[valG + = 1 + 1 + 1 + 1 + 0 + 0\] \[\rightarrow valG = 2 + 4 = 6\]
Thêm cạnh \((4,5)\)		\[valG + = 1 + 1 + 2 + 2 + 2\] \[\rightarrow valG = 6 + 8 = 14\]
Thêm cạnh \((3,5)\)		\[valG + = 1 + 1 + 2 + 2 + 2\] \[\rightarrow valG = 14 + 8 = 22\]

Giá trị của đồ thị là \(valG = 22\)

• Nếu thêm các cạnh của đồ thị theo thứ tự \((3,4);(4,5);(1,2);(3,5)\) thì giá trị của đồ thị:

Đồ thị ban đầu		\[valG = 0\]
Thêm cạnh \((3,4)\)		\[valG + = 0 + 0 + 1 + 1 + 0\] \[\rightarrow valG = 0 + 2 = 2\]
Thêm cạnh \((4,5)\)		\[valG + = 0 + 0 + 2 + 2 + 2\] \[\rightarrow valG = 2 + 6 = 8\]
Thêm cạnh \((1,2)\)		\[valG + = 1 + 1 + 2 + 2 + 2\] \[\rightarrow valG = 8 + 8 = 16\]
Thêm cạnh (3,5)		\[valG + = 1 + 1 + 2 + 2 + 2\] \[\rightarrow valG = 16 + 8 = 24\]

Giá trị của đồ thị trong trường hợp này là \(valG = 24\). Đây cũng là giá trị lớn nhất đồ thị nhận được.

Dữ liệu vào:

+ Dòng đầu tiên ghi 2 số nguyên dương \(n,\ m\ (1 \leq n \leq 10^{5};0 \leq m \leq {2 \times 10}^{5})\) lần lượt là số đỉnh của đồ thị \(G\) và số cạnh trong tập \(X\)

+ \(m\) dòng tiếp theo, dòng thứ \(i\) ghi 2 số nguyên dương \(u_{i},\ v_{i}\ (1 = 1\ldots m;1 \leq u_{i},\ v_{i} \leq n;u_{i} ≠ v_{i})\) cho biết một cạch trong tập \(X\)

Kết quả: ghi một số nguyên duy nhất là giá trị lớn nhất của đồ thị \(G\).

Ví dụ:

Input	Output
5 4 1 2 3 4 4 5 3 5	24

Ràng buộc:

+ 30% số test tương ứng 30% số điểm có \(m \leq 10\)

+ 30% số test khác tương ứng 30% số điểm có \(m\) cạnh tạo thành đồ thị liên thông

+ 40% số test còn lại không có ràng buộc gì thêm.