Đấ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