III Obóz im. A. Kreczmara 2002

Zadanie: ogr
Autor: Marcin Stefaniak
Ogród

dzień pierwszy 5 sierpnia 2002
Plik źródłowy: ogr.??? (np. pas, c, cpp)
Plik wejściowy: ogr.in
Plik wyjściowy: ogr.out

Architekt Numernabis buduje pałac dla Cezara. Rzecz jasna, taki pałac nie może się obejść bez wspaniałego kolistego ogrodu. W ogrodzie wytyczono ścieżki. Ścieżki spotykają się w skrzyżowaniach. Każda ścieżka łączy dwa różne skrzyżowania albo prowadzi od skrzyżowania do jednego z wyjść z ogrodu. Do każdego z wyjść prowadzi dokładnie jedna ścieżka. Z jednego skrzyżowania prowadzi najwyżej jedna bezpośrednia ścieżka do wyjścia. Ścieżki nie przecinają się, nie ma też tuneli ani estakad. Z każdego skrzyżowania można dojść wzdłuż ścieżek do każdego innego skrzyżowania oraz do wyjścia.

Poletka między ścieżkami mogą być obsadzone palmami, kwiatami albo też oliwkami (na więcej nie pozwala klimat i umiejętności Numernabisa). Każde poletko będzie obsiane jednym rodzajem roślinności.

Ponieważ są 3 rodzaje roślin, więc Numernabis (a jest on nowoczesnym architektem) zaplanował, że w każdym skrzyżowaniu zejdą się dokładnie 3 ścieżki. Co więcej, zamierza on tak rozplanować roślinność, żeby w każdym skrzyżowaniu spotykały się pola obsiane wszystkimi trzema rodzajami roślin ozdobnych. Coś mu jednak nie wychodzi, może nie da się tego zrobić?

Pomóż biednemu Numernabisowi i uratuj go od krokodyli! Napisz program, który wyznaczy, czy dla danego planu ogrodu da się tak posadzić rośliny, jak wymaga nowoczesna sztuka konstruowania ogrodów.

Wejście

W pliku ogr.in znajduje się opis ogrodu:

Wyjście

Plik wyjściowy ogr.out powinien zawierać odpowiedź - jedno słowo TAK lub NIE, będące odpowiedzią na pytanie, czy w ogrodzie da się tak posadzić roślinność, jak chce architekt.

Przykład

Dla pliku wejściowego ogr.in:

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

poprawną odpowiedzią jest plik wyjściowy ogr.out:

TAK