Đất nước xinh đẹp ~X~ có ~N~ thành phố và có ~M~ mối quan hệ kinh tế giữa các thành phố. Mối quan hệ kinh tế này là song phương, do đó thành phố ~u~ có mối quan hệ kinh tế với thành phố ~v~ tức là thành phố ~v~ có mối quan hệ kinh tế với ~u~.
Tổng thống của nước ~X~ muốn chia đất nước của mình thành ~K~ bang nhỏ ~(N~ chia hết cho ~K)~, nhưng ông lại muốn tối thiểu hóa quan hệ kinh tế giữa các bang với nhau. Tổng số lượng quan hệ kinh tế giữa các bang là số lượng cặp ~(u~, ~v)~ với thành phố ~u~, ~v~ thuộc ~2~ bang khác nhau và có mối quan hệ kinh tế với nhau
Do đó nhiệm vụ được đặt ra là: Chia ~N~ thành phố thành ~K~ bang sao cho:
- Mỗi bang có số lượng thành phố bằng nhau
- Tổng số lượng quan hệ kinh tế giữa các bang là nhỏ nhất.
Input
- Dòng ~1~: chứa ~3~ số nguyên dương ~N~, ~M~ và ~K~ ~\left(1 \leq N \leq 500, 0 \leq M \leq \frac{N \times (N - 1)}{2}\right)~.
- ~M~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~u~ và ~v~ thể hiện có mối quan hệ kinh tế trực tiếp giữa ~u~ và ~v~.
Output
- Dòng ~1~: Tổng số lượng quan hệ kinh tế giữa các bang.
- ~K~ dòng tiếp theo, dòng thứ ~i~ gồm ~\frac{N}{K}~ số nguyên dương là các thành phố thuộc bang thứ ~i~
Giới hạn
- Gọi Tổng số lượng kinh tế giữa các bang của lời giải ban tổ chức là ~X~
- Gọi Tổng số lượng kinh tế giữa các bang của lời giải bạn là ~Y~
- Gọi ~P~ là số điểm của test.
- Điểm của bạn nhận được là ~\min \left(\frac{X+1}{Y+1} \times P \times 95\%, P \right)~
Sample Input
6 10 3
1 3
1 4
2 3
2 4
2 5
2 6
3 4
3 5
4 5
4 6
Sample Output
Output 1:
9
1 2
3 4
5 6
Output 2:
8
1 4
2 5
3 6
Note
Giả sử tổng số lượng kinh tế giữa các bang của ban tổ chức là ~9~, và điểm của test là ~1~ điểm:
- Với Output 1: Bạn được ~0.95~ điểm
- Với Output 2: Bạn được ~1~ điểm
Comments