시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 8 | 1 | 1 | 100.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 b ( 1 <= a, b <= N, a 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".
3 2 1 1 2 3 2 2 1 3 1 3 2 1 2 2 3
TAK 1 2 TAK 30 6 5 NIE
Contest > Spot > HotSpot 2011 2-4번