Program Buses; Const MaxN=100000; MaxM=100000; MaxK=100000; Var K: LongInt; // количество дуг во всех маршрутах вместе N, M: LongInt; data: Array [1..MaxN, 1..2] of LongInt; index, stopindex: Array [1..MaxM] of LongInt; // характеристики вершин prev: Array [1..MaxK] of LongInt; // начала стрелок f: Text; i, j, w, a, a0: LongInt; stack1, stack2: Array [1..MaxK+1] of LongInt; top1, top2: LongInt; Begin {INPUT} Assign(f, 'rhodo.in'); Reset(f); Readln(f, N, M); For i:= 1 To M Do Begin index[i]:= 0; End; K:= 0; For i:= 1 To N Do Begin Read(f, w); Read(f, a0); a:= a0; For j:= 2 To w Do Begin Inc(K); data[K,1]:= a; Read (f, a); data[K,2]:= a; Inc(index[a]); End; Inc(K); data[K,1]:= a; data[K,2]:= a0; Inc(index[a0]); Readln(f); End; Close(f); // сейчас index[i] - количество стрелок, входящих в i stopindex[1]:= index[1]; For i:= 2 To M Do Begin Inc(index[i], index[i-1]); stopindex[i]:= index[i]; End; // а теперь index[i] и stopindex[i] - номер последней ячейки в i-ом отрезке // массива prev - массива начальных вершин стрелок, заканчивающихся в i {Заполняем массив prev} For j:= 1 To K Do Begin a:= data[j,2]; prev[index[a]]:= data[j,1]; Dec(index[a]); End; For i:= 1 To M Do Begin Inc(index[i]); End; // Сейчас index[i] стал номером ПЕРВОЙ ячейки в i-ом отрезке массива // prev - массива начальных вершин стрелок, заканчивающихся в i; // в stopindex[i] по-прежнему хранятся номера ПОСЛЕДНИХ ячееек. {Ищем, с чего начать} i:= 0; Repeat Inc(i); Until index[i]<=stopindex[i]; {ПОЕХАЛИ! Строим Эйлеров цикл с помощью двух стеков} top1:= 1; stack1[1]:= i; top2:= 0; Repeat While index[i]<=stopindex[i] Do Begin a:= prev[index[i]]; Inc(index[i]); Inc(top1); stack1[top1]:= a; i:= a; End; Inc(top2); stack2[top2]:= stack1[top1]; Dec(top1); i:= stack1[top1]; Until top1=0; Assign(f, 'rhodo.out'); Rewrite(f); If top2>K Then Begin Write(f, K); For i:= 1 To K Do Write(f,' ',stack2[i]); End Else Begin Writeln(f, 'impossible'); End; Close(f); End.