Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MWP2_2G - Wycieczka

Mały Jasio żyje w przyszłości w wielkiej metropolii, gdzie można się poruszać od przystanku do przystanku pojazdami komunikacji miejskiej, zwanymi polibusami. Ze względu na różne zagrożenia cywilizacyjne (np. terroryzm, ptasia lub świńska grypa, choroba szalonych krów, globalne ocieplenie), komunikacja ta funkcjonuje w ten sposób, że po dojechaniu do dowolnego przystanku zawsze trzeba wysiadać z polibusu, który w tym czasie zostanie sprawdzony i zdezynfekowany przez odpowiednie służby miejskie. Jeżeli podróż powinna trwać dalej, to trzeba się przesiadać - nawet wtedy, gdy będziemy kontynuować dalszą drogę tym polibusem, z którego właśnie wysiedliśmy.

Mama Jasia wybiera się na zakupy, zabierając syna ze sobą. Ponieważ galerie handlowe znajdują się obok przystanków komunikacji miejskiej, dlatego przed wyruszeniem w trasę, mama robi listę przystanków, do których może się udać na zakupy, numerując je kolejnymi liczbami naturalnymi.

Ponieważ Jasio jest dużym chłopcem, dlatego mama będąc w sklepie czasami pozwala mu w tym czasie robić wycieczki po mieście do tych przystanków, które znajdują się na jej liście. Oczywiście Jasio mówi mamie dokąd zamierza dotrzeć. Po zakupach mama Jasia jedzie po niego w umówione miejsce.

Jasio jest oryginałem, dlatego w trakcie każdej z wycieczek dokładnie jeden raz się przesiada - nawet wtedy, gdy jego wycieczka zakończy się w punkcie startu. Tymczasem mama nie znosi się przesiadać - najchętniej nigdzie by po syna nie jeździła - dlatego zgodę na wycieczkę daje tylko wtedy, gdy ma pewność, że w drodze po syna nie będzie się przesiadać.

Jeszcze przed wyruszeniem w drogę, nie wiedząc dokąd uda się na zakupy, mama musi podjąć decyzję, czy ewentualnie może zgodzić się na wycieczkę syna. Dopiero po tej decyzji następuje wybór miejsca zakupów.

Ponieważ nie jest łatwo zdecydować, czy Jasio będzie mógł udać się na wycieczkę, jego mama liczy na Twoją pomoc. W tym celu musisz napisać odpowiedni program, który pomoże tę decyzję podjąć. Potraktuj listę przystanków wybranych przez mamę Jasia jako węzły grafu, zaś możliwe połączenia pomiędzy nimi jako jego łuki. Powyższy graf będziemy dalej nazywać grafem MJ (od: graf mamy Jasia)

Napisz program, który dla każdego zestawu danych będzie sprawdzał, czy w przypadku potencjalnej wycieczki Jasia (z jedną przesiadką), jego mama nie będzie musiała się przesiadać. Należy założyć, że zgodę na wycieczkę Jasio otrzymuje tylko wtedy, gdy istnieje niepusty zbiór jego możliwych wycieczek.

Wejście

Pierwsza linijka wejścia zawiera dokładnie jedną liczbę całkowitą d, 1 ≤ d ≤ 1000, określającą liczbę zestawów danych. Każdy zestaw zaczyna się liczbą n, 2 ≤ n ≤ 100 będącą liczbą przystanków, następnie w zestawie danych pojawia się macierz o rozmiarze n × n będąca macierzą sąsiedztwa grafu MJ.

Wyjście

W d liniach wyjścia należy podać dla każdego i-tego zestawu odpowiedź TAK lub NIE będącą odpowiedzią na pytanie, czy w grafie MJ, każdej marszrucie zawierającej jedną przesiadką odpowiada marszruta nie zawierająca żadnej przesiadki.

Przykład

Wejście:

3
2
0 1
1 0
2
0 0
1 0
3
0 1 1
0 0 1
0 0 0

Wyjście:

TAK
NIE
TAK

Dodane przez:Maciej Boniecki
Data dodania:2010-01-13
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: NODEJS OBJC PERL6 SCM qobi SQLITE VB.NET
Pochodzenie:II Mistrzostwa WWSI w Programowaniu

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.