시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

Hektor uwielbia zadawać Wiktorowi wszelkiej maści zagadki. Dziś Wiktora czeka zadanie szczególnie trudne, bo jego kolega wymyślił zupełnie nowy rodzaj łamigłówek.

Hektor napisał na kartce N różnych niezerowych liczb naturalnych i każdą z nich otoczył kółkiem. Następnie narysował strzałki prowadzące od liczby a do liczby b dla każdej pary takich liczb (a,b), że a dzieli b. Na końcu Hektor zamazał liczby wpisane do kółek.

Łamigłówka polega na znalezieniu N różnych niezerowych liczb naturalnych i przypisaniu ich do pól tak, aby narysowane przez Hektora strzałki się zgadzały, tj. łączyły wszystkie te (i żadne inne) pary liczb, w których liczba na początku strzałki dzieli liczbę na końcu strzałki.

Uwaga: Wszystkie liczby w znalezionym rozwiązaniu muszą mieć nie więcej niż tysiąc cyfr (przy czym gwarantujemy, że dla każdych spełniających ograniczenia danych wejściowych, dla których istnieje poprawne rozwiązanie, istnieje również poprawne rozwiązanie w którym wszystkie liczby mają nie więcej niż sto cyfr, więc jest to ograniczenie dość luźne). 

입력

W pierwszej linii wejścia znajduje się liczba naturalna Z ( 1 <= Z <= 10 ) opisująca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.

Pierwsza linia zestawu składa się z liczb N oraz M ( 1 <= N <= 50, 0 <= M ), oznaczających kolejno liczbę kółek do uzupełnienia oraz liczbę strzałek narysowanych przez Hektora. W kolejnych M wierszach opisane są strzałki. Opis strzałki składa się z dwóch różnych, oddzielonych od siebie spacją liczb naturalnych a i ( 1 <= ab <= Na różne od b), oznaczających odpowiednio: numer początkowego kółka strzałki i numer końcowego kółka strzałki. Lista nie będzie zawierać powtarzających się strzałek.

출력

Dla każdego zestawu, jeśli istnieje sposób prawidłowego przypisania liczb do kółek, należy w pierwszej linii wypisać słowo "TAK", a następnie w N kolejnych liniach wypisać liczby przyporządkowane do poszczególnych pól, w kolejności od pierwszego do N-tego pola. Każda wypisana liczba musi mieć nie więcej niż tysiąc cyfr. 

Jeśli rozwiązanie nie istnieje, należy w osobnej linii wypisać słowo "NIE".

예제 입력 1

3
2 1
1 2
3 2
2 1
3 1
3 2
1 2
2 3

예제 출력 1

TAK
1
2
TAK
30
6
5
NIE

출처

Contest > Spot > HotSpot 2011 2-4번