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 ≤ 200 ≤ M ≤ N(N-1)/2- Se garantează că există mereu o soluție
- Se va accepta orice soluție corectă
- Pentru
60de puncte1 ≤ 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.