VNOI Marathon 2015

Đấ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 (1 ≤ N ≤ 500, 0 ≤ M ≤ N * (N - 1) / 2).

• 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 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