Ordine di Mungitura (Gold)#10388
Le mucche di Farmer John, numerate da a come sempre, hanno a quanto pare troppo tempo libero tra gli zoccoli. Di conseguenza, hanno elaborato una complessa gerarchia sociale legata all'ordine in cui Farmer John le munge ogni mattina.
Dopo settimane di studio, Farmer John ha fatto osservazioni sulla struttura sociale delle sue mucche. Ogni osservazione è una lista ordinata di alcune delle sue mucche, il che significa che queste mucche dovrebbero essere munte nello stesso ordine in cui compaiono nella lista. Per esempio, se una delle osservazioni di Farmer John è la lista , Farmer John dovrebbe mungere la mucca in un certo momento prima della mucca , e la mucca in un certo momento prima della mucca .
Le osservazioni di Farmer John sono prioritizzate, quindi il suo obiettivo è massimizzare il valore tale che il suo ordine di mungitura soddisfi le condizioni date dalle prime osservazioni. Se più ordini di mungitura soddisfano queste prime condizioni, Farmer John segue una tradizione di lunga data secondo cui le mucche con numeri più piccoli hanno la precedenza sulle mucche con numeri più grandi, quindi vorrebbe mungere prima le mucche con i numeri più bassi. Più formalmente, se più ordini di mungitura soddisfano queste condizioni, Farmer John vorrebbe usare quello lessicograficamente più piccolo. Un ordine è lessicograficamente più piccolo di un ordine se esiste tale che x_i = y_i per tutti gli i < j e x_j < y_j (in altre parole, i due ordini coincidono fino a una certa posizione, in cui ha un elemento più piccolo di ).
Aiuta Farmer John a determinare l'ordine migliore in cui mungere le sue mucche.
La prima riga contiene due interi e m~(1 \le n \le 10^5, 1 \le m \le 5 \cdot 10^4). Ciascuna delle successive righe descrive un'osservazione: la (i + 1)-esima riga descrive l'osservazione e inizia con il numero m_i di mucche nell'osservazione, seguito da m_i interi — i numeri di queste mucche nell'ordine richiesto. La somma di tutti gli m_i non supera 2 \cdot 10^5.
Stampa interi — una permutazione dei numeri da a che specifica l'ordine in cui Farmer John dovrebbe mungere le sue mucche.
Qui, Farmer John ha mucche. Dovrebbe mungere la mucca prima della mucca , e la mucca prima della mucca (la prima osservazione); la mucca prima della mucca (la seconda osservazione); e la mucca prima della mucca , e la mucca prima della mucca (la terza osservazione). Le prime due osservazioni possono essere soddisfatte simultaneamente, ma Farmer John non può soddisfarle tutte e tre contemporaneamente, poiché ciò richiederebbe che la mucca venga prima della mucca e che la mucca venga prima della mucca .
Pertanto, ci sono due ordini che soddisfano le prime due osservazioni: 1, 4, 2, 3 e 4, 1, 2, 3; il primo è lessicograficamente più piccolo.
Esempio 1