USACO 2022 December Contest, Gold, Strongest Friendship Group

Xem PDF

Điểm: 1000 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Nông dân John có \(N\) con bò \((2 \le N \le 10^5)\), được đánh số \(1 \dots N\). Có \(M\) \((1 \le M \le 2 \times 10^5)\) cặp bạn bè giữa những chú bò này.

Một nhóm bò được gọi "nhóm bạn thân" nếu như giữa hai chú bò bất kì đều có thể quen nhau thông qua một chuỗi các cặp bạn bè cùng nằm trong nhóm (tình bạn với các chú bò ngoài nhóm không có ảnh hưởng gì). "Sức mạnh" của một nhóm bạn bè là số lượng bạn bè ít nhất của chú bò bất kì nhân với số lượng bò trong nhóm (lần nữa, bạn bè ngoài nhóm không được tính nhé!!).

Tính sức mạnh lớn nhất trong tất cả các nhóm bạn thân.

Input

  • Dòng đầu tiên gồm hai số \(N\)\(M\).
  • \(M\) dòng tiếp theo là \(2\) số \(u_i, v_i\) thể hiện rằng chú bò \(u_i\) là bạn với chú bò \(v_i\) \((1 \le u_i, v_i \le N, u_i \ne v_i)\). Không có cặp nào xuất hiện quá một lần.

Output

  • Gồm một dòng là sức mạnh lớn nhất trong tất cả các nhóm bạn thân.

Scoring

  • Subtask \(1\): \(N \le 16\).
  • Subtask \(2\): \(N \le 1000\).
  • Subtask \(3\): Không có ràng buộc gì thêm.

Test 1

Input
8 10
1 2
1 3
1 4
2 3
2 4
3 4
1 5
2 6
3 7
4 8
Output
12
Note

Sức mạnh lớn nhất có thể đạt được là của nhóm bò gồm \(1\), \(2\), \(3\), \(4\). Mọi chú bò đều có ít nhất \(3\) bạn trong nhóm nên đáp án là \(3 \times 4 = 12\).


Bình luận

Không có bình luận nào.