Dorind să se angajeze, Arius M. a fost nevoit să dea un interviu în care a primit următoarea problemă simplă: dându-se N şiruri crescătoare de numere întregi, să se determine cel mai lung subşir comun al acestora.

Cerinţă

Rezolvaţi această problemă pe care Arius M. a considerat-o destul de uşoară.

Date de intrare

Pe prima linie a fişierului ausoara.in se află N, numărul şirurilor. Următoarele N linii descriu cele N şiruri. Linia i este formată din Mi, numărul elementelor şirului curent, urmat de Mi numere, reprezentând elementele şirului i.

Date de ieşire

Fişierul de ieşire ausoara.out va conţine pe prima linie T, numărul elementelor celui mai lung subşir comun al celor N şiruri. Urmează T numere întregi ce descriu elementele subşirului comun de lungime maximă.

Restricţii

• 0 < N < 101
• 0 < Mi < 1001
• Dacă avem un şir de numere a1, a2, …, an atunci numim subşir un şir de forma ai1, ai2, …, aik cu i1, i2, …, ik aparţinând mulţimii {1, 2, …, n} şi i1 < i2 < ... < ik.
• Elementele şirurilor sunt numere întregi în intervalul [1, 1 000 000].
• Elementele fiecărui şir sunt date în ordine crescătoare.
• Pentru 60% din teste, elementele fiecărui şir sunt distincte.
• Pentru 90% din teste, elementele şirurilor sunt în intervalul [1, 10 000].

Exemple

ausoara.in	ausoara.out
1 3 1 2 3	3 1 2 3
2 2 1 2 2 2 3	1 2
3 6 1 2 2 3 5 5 9 2 2 2 2 2 5 5 5 7 9 2 2 2 4 5 7 7 7 7	3 2 2 5
3 3 1 2 3 3 4 5 6 3 7 8 9	0
3 3 1 1 1 1 1 2 1 1	1 1

autor: Student Marius Stroe

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com