Cerința

În cadrul unui experiment de inginerie genetică, un grup de cercetători desfășoară seturi de analize ample asupra unei secțiuni a genomului uman. Scopul studiului este selectarea unor succesiuni optime de hibridizări dintre doi cromozomi.

Genomul analizat are în componența sa n cromozomi interconectați prin mecanisme de crossing-over unidirecțional ce permit schimburi eficiente de gene care favorizează apariția mutațiilor și evoluția per ansamblu a genomului. Fiecare mecanism de crossing-over are un coeficient specific de transfer, c, care se definește prin numărul de gene pe care le poate transmite la un moment dat de la cromozomul x la cromozomul y.

Interesul cercetătorilor se concentrează asupra unei perechi speciale de cromozomi, u și v. Se definește drept succesiune validă de cromozomi o succesiune care începe cu cromozomul u, se termina cu cromozomul v și nu conține de 2 ori același cromozom. Se cere identificarea primelor k succesiuni valide din punct de vedere al sumelor coeficienților de transfer.

Succes!

Date de intrare

Pe prima linie a fișierului de intrare chromosome.in se află valorile: n – numărul de cromozomi per secțiunea de genom, m – numărul de mecanisme de crossing-over, k – numărul maxim de succesiuni de recombinări care trebuie determinate, u și v – perechea de cromozomi speciali.

Pe următoarele m linii se află câte o tripletă de forma x, y, c definită astfel: există mecanism de transfer unidirecțional de la cromozomul x la cromozomul y având coeficientul specific c.

Date de ieșire

Pe prima linie a fișierului de ieșire chromosome.out se va afișa valoarea r – numărul de succesiuni de combinări găsite (k sau mai puține), iar pe următoarele linii descrierile succesiunilor:

• pe prima linie a succesiunii i se vor afișa două valori: \(c_i\) – costul succesiunii i și \(p_i\) – numărul de cromozomi implicați în succesiunea i;
• pe a doua linie a setului i se vor afișa cei \(p_i\) cromozomi în ordinea în care aceștia apar în succesiunea i

Restricții și precizări

• Se garantează pentru fiecare test că există cel puțin o succesiune de recombinări între cromozomii u și v;
• Succesiunile se vor afișa în ordine crescătoare a costurilor, iar la costuri egale în ordine colexicografică a cromozomilor implicați;
• În cazul în care nu există k succesiuni se vor afișa doar cele găsite;
• 1 <= n <= 1000;
• 1 <= m <= 8000;
• 1 <= c <= 10000;
• 1 <= k <= 500;
• 1 <= u, v, x, y <= n.

Exemplu

chromosome.in

6 8 4 6 4
5 3 3
5 1 1
6 5 1
2 1 4
2 6 3
3 4 2
1 3 1
6 1 2

chromosome.out

3
5 5
6 5 1 3 4 
5 4
6 1 3 4 
6 4
6 5 3 4