Lara a rămas blocată într-o peșteră cu un sistem elaborat de camere. Ea bănuiește că ieșirea s-ar afla în una din cele N camere, dar nu știe sigur dacă peștera are vreo ieșire sau în ce cameră ar fi. Pentru a intra în fiecare cameră are nevoie de câte o cheie. Mai mult, pentru ca unele camere să fie accesibile, ea trebui să fi deblocat deja alte camere. Odată introdusă cheia într-o ușă, dacă camera este de fapt ieșirea, Lara va putea părăsi peștera în acel moment; altfel camera se va deschide ziua următoare.

Uitându-se mai atent prin peșteră, Lara descoperă că atunci când razele soarelui bat într-o anumită poziție, K chei apar în dreptul statuilor din peșteră pentru o perioadă foarte scurtă de timp. Ea nu este obligată să ia toate cheile dintr-o zi, dar dacă ia o cheie trebuie să o folosească în ziua respectivă pentru a nu supăra spiritele din peșteră.

Hotărâtă să descopere misterele lumii, ea își face un plan de scăpare. Ajutați-o să afle durata minimă a planului (în zile) și camerele pe care le deschide în fiecare zi în cel mai rău caz posibil pentru ea.

Date de intrare

Pe prima linie se află N - numărul de camere, M, K - numărul de chei disponibile zilnic. Pe următoarele M linii urmează două numere x y cu semnificația că camera x trebuie să fie mai întâi deblocată pentru a deschide camera y.

Date de ieșire

Se va afișa pe prima linie durata minimă a planului. Pe următoarele linii, se vor scrie pe linia i + 1 camerele deschise în ziua i, separate prin spații.

Restricții și precizări

• 1 ≤ N ≤ 20
• 0 ≤ M ≤ N(N-1)/2
• Se garantează că există mereu o soluție
• Se va accepta orice soluție corectă
• Pentru 60 de puncte 1 ≤ N ≤ 15
• Se acordă 60% din punctaj doar pentru numărul de zile

Exemplu

stdin

9 9 3
1 2
3 2
4 8
4 5
8 2
5 2
6 7
6 9
4 2

stdout

3
1 3 4
5 6 8
2 7 9

Explicații

Planul sistemului de camere arată astfel:



În prima zi deschide camerele 1, 3, 4. Nu poate deschide mai multe camere deoarece are la dispoziție doar 3 chei. Camera 4 trebuie deschisă înaintea (în una din zilele precedente) camerei 2, deci nu poate deschide camera 2. În a doua zi deschide camerele 5, 6, 8, iar în a treia zi restul camerelor.