beecrowd | 1979

Separate Rooms

By Anderson Chaves, UNIFESO BR Brazil

Timelimit: 1

Luiz is a very dedicated coordinator of the computer science course. He knows the importance of encouraging their students to study algorithms, so decided to hold a individual programming contest between them, with awards.

Luiz would like to avoid as much as possible the possibility of fraud in the competition, and so wouldn't want two candidates had friends in the same room during the proof.

Unfortunately Luiz has only two classrooms for realize the proof, but fortunately he know very well their students, and can tell easily who is friends with whom. However, he needs to know if it is possible, with only two classrooms available, combining the students so that friends don't stay together, for this, he called to you, dedicated student of the course, to create a program to help him.

Input

The input consists of several test cases. The first line of each test case consists of an integer N (2 ≤ N ≤ 100) indicating the number of students who will perform the proof.
Each N couple of these lines describes the friendly relations of each participant, so that the first line consists of the participant's ID, and the next line consists of a list describing an M number of students (1 ≤ M < N) with which one participant has a relationship of friendship.
You can consider that it not relevant the number of people willing in each room, and that if there is a friendship between the students x and y there is a friendly relationship between y and x. The entry ends when N = 0, and should not be processed.

Output

For each test case you should print a line containing the "SIM" answer, if possible have the students so that there are no two friends doing the proof in the same classroom, and "NAO" otherwise.

Input Sample Output Sample

6
1
2 3
2
1 4
3
1 6
4
2 5
5
4 6
6
3 5
4
1
2 3 4
2
1
3
1
4
1
4
1
2 4
2
4
3
4
4
1 2 3
0

SIM
SIM
NAO

Contest Balões na Serra