VIII Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 29.05.2004

Opis

W każdej powieści kryminalnej danych jest trochę faktów, które trzeba ze sobą powiązać w jakąś logiczną całość, by rozwiązać zagadkę. Łatwość powiązania ich ze sobą przez czytelnika zależy w dużej mierze od kolejności ich występowania w kryminale.

Najlepsze kryminały mają tę charakterystyczną cechę, że fakty w nich przedstawione mówią dużo i niewiele z nich trzeba ze sobą powiązać by rozwiązać zagadkę, ale mimo tego, kolejność występowania faktów tak dobrze maskuje prawdę, że bardzo trudno wpaść na rozwiązanie. Ogromną sztuką jest napisanie kryminału, w którym powiązanie dowolnej pary faktów daje rozwiązanie, a i tak jedynie bardzo inteligentni czytelnicy są w stanie rozwiązać zagadkę. Właśnie konstrukcję takich kryminałów będziemy tutaj rozważać.

Zadanie

Mając dane poziomy inteligencji niezbędne do skojarzenia niektórych par faktów w zależności od ich względnego położenia, należy podać w jakiej kolejności powinny występować fakty, by poziom inteligencji potrzebny do rozwiązania zagadki był jak największy. Należy podać również ten poziom inteligencji.

Specyfikacja wejścia

W pierwszym wierszu wejścia podana jest dodatnia liczba całkowita D (D ≤ 50), oznaczająca liczbę zestawów danych, które dalej pojawią się na wejściu. W pierwszym wierszu każdego zestawu znajdują się dwie liczby całkowite N i M (2 ≤ N ≤ 10.000, 1 ≤ M ≤ 30.000), oznaczające odpowiednio liczbę faktów oraz liczbę reguł opisujących zależność między nimi. W kolejnych M wierszach zapisane są reguły złożone z 4 liczb całkowitych: A, B, x i y (1 ≤ A, B ≤ N, A ≠ B, 0 ≤ x, y ≤ 1.000.000.000). Taka reguła oznacza, że minimalny poziom inteligencji potrzebny do powiązania faktów o numerach A i B jest równy x jeśli A jest przedstawiony w kryminale przed B, a y w przeciwnym wypadku. Na wejściu występuje co najwyżej jedna reguła dotycząca jednej pary faktów, a jej brak oznacza, że faktów nie można ze sobą powiązać.

Specyfikacja wyjścia

Dla każdego zestawu danych należy wypisać jeden wiersz zawierający N+1 liczb całkowitych oddzielonych spacjami. Pierwsza z nich ma być minimalną inteligencją czytelnika, niezbędną do rozwiązania zagadki, przy możliwie najtrudniejszej kolejności faktów (tj. takiej kolejności, by ta inteligencja musiała być jak największa). Pozostałe N liczb powinno być permutacją liczb całkowitych od 1 do N, reprezentującą tą kolejność faktów. W przypadku istnienia kilku rozwiązań optymalnych można wypisać dowolne z nich.

Przykład

3
2 1
1 2 3 4
3 3
1 2 2 1
2 3 2 1
3 1 3 2
5 4
1 2 10 3
2 4 20 4
4 5 30 5
2 5 1 6

4 2 1
2 1 2 3
5 1 3 5 2 4