Trung vị điểm kiểm tra

Buổi 06 — Sắp xếp & Tìm kiếm Buổi 08 — Contest Chặng 1 sorting
Points
10
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved