7926번 - Chciwi rolnicy 다국어

Kraje Bajtocji postanowiły się zjednoczyć i stworzyć Unię Krajów Bajtów. Jedną z pierwszych zasad miały stać się dopłaty bezpośrednie do rolnictwa. W związku z tym każdy rolnik otrzyma pewną liczbę naturalną, oznaczającą wielkość gospodarstwa, które posiada. Liczba ta przekładałaby się wprost na wysokość otrzymywanych dopłat. Dążąc do zmniejszenia różnic społecznych parlament postanowił płacić najwięcej gospodarzom o najniższych numerach, zaczynając od zera. Oczywiście w ten sposób każdy gospodarz przydzieliłby sobie wartość zero i cała reforma niewiele by dała. Dlatego też dopisano do ustawy jeden warunek, jaki musi spełniać to przyporządkowanie. Każdemu gospodarzowi należy przypisać najmniejszą liczbę naturalną różną od wszystkich liczb przydzielonych jego pracownikom. Okazało się jednak, że bywają przypadki, w których nie da się wygenerować takiego przyporządkowania w sposób jednoznaczny (lub wcale się nie da), dlatego dopisano w erracie jeszcze jeden podpunkt, który stosuje się zawsze w takich przypadkach. Wprowadzono mianowicie wartość nieskończoność. Oznacza ona, że rolnik X ma pracownika Y , który także ma wartość nieskończoność i żaden z pracowników Y nie ma przypisanej wartości skończonej, którą gospodarz X chciałby zająć dla siebie. Rząd Bajtocji chce, aby przyporządkowanie zawierało jak najwięcej nieskończoności. Związek Rolny postanowił zlecić Ci napisanie programu wyznaczającego przydział wartości, który spełni wszystkie te wymagania.

W pierwszej linii wejścia znajduje się liczba t (1 ≤ t ≤ 100) określająca liczbę zestawów testowych. W kolejnych liniach znajduje się opis t zestawów testowych. Każdy zestaw rozpoczyna się od dwóch liczb n, m (1 ≤ n ≤ 100, 0 ≤ m < 10000), oznaczających kolejno liczbę gospodarzy w Unii Krajów Bajtów oraz liczbę istniejących pomiędzy nimi powiązań biznesowych. W kolejnych m liniach następuje opis powiązań. Każde powiązanie reprezentują dwie liczby a, b (1 ≤ a, b ≤ n), które określają, że gospodarz a zatrudnia gospodarza b.

Dla każdego testu należy podać w kolejnych n liniach wartości, jakie powinni sobie przypisać kolejni rolnicy. W przypadku przypisania nieskończoności należy wypisać -1.