Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VMGROUP2 - Phân nhóm đồ thị

Đấ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 K (1 ≤ N ≤ 500, 0 ≤ MN * (N - 1) / 2).
  • M dòng tiếp theo, mỗi dòng chứa 2 số nguyên uv thể hiện có mối quan hệ kinh tế trực tiếp giữa uv.

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 N/K số nguyên dương là các thành phố thuộc bang thứ i

Chấm điểm

  • Trong quá trình thi, bài của bạn được chấm với 15% test. Sau khi kỳ thi kết thúc, bài của bạn sẽ được chấm lại với toàn bộ 100% test.
  • Cách tính điểm mỗi test:
    • 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
    • Điểm của bạn nhận được là (X + 1) / (Y + 1)
  • Sau khi thi, điểm của bạn sẽ được tính lại theo % so với thí sinh cao điểm nhất.
  • Các bạn không được phép nộp quá 20 lần, nếu bạn nộp quá 20 lần thì chúng mình sẽ không tính kết quả của bạn.
  • Bạn được phép nộp bài nhiều lần, kết thúc kỳ thi điểm lần nộp bài cuối của bạn sẽ là điểm của bạn.

 

Example

Input:

6 10 3
1 3
1 4
2 3
2 4
2 5
2 6
3 4
3 5
4 5
4 6

Output 1:

9
1 2
3 4
5 6

Output 2:

8
1 4
2 5
3 6

Giả sử tổng số lượng kinh tế giữa các bang của ban tổ chức là 9:

  • Với Output 1: Bạn được 1 điểm
  • Với Output 2: Bạn được 1.11 điểm

Được gửi lên bởi:VOJ Team
Ngày:2015-08-12
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:VM15 - khanhptnk

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.