Trung vị điểm kiểm tra
Points
10
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho một đồ thị vô hướng đơn gồm $N$ đỉnh và $M$ cạnh. Hãy kiểm tra xem đồ thị đã cho có phải là đồ thị hai phía (bipartite) hay không.
Nếu đồ thị không phải là đồ thị hai phía, in ra -1. Ngược lại, hãy tính số lượng cạnh tối đa có thể thêm vào đồ thị (không tạo cạnh song song hay khuyên) sao cho đồ thị vẫn giữ nguyên tính chất là đồ thị hai phía.
Dữ liệu vào
Giá trị trung vị, làm tròn đến 1 chữ số thập phân.
Ví dụ
- Dòng đầu tiên gồm hai số nguyên $N, M$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$).
- $M$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $u, v$ ($1 \le u, v \le N$, $u \neq v$).
Dữ liệu ra
| Input | Output |
|---|---|
| 5 10 2 8 4 6 |
6.0 |
| 4 10 4 6 8 |
7.0 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le a_i \le 10^9$
Community Discussion