#include <string.h>
#include <stdio.h>
#define MAXN 100
#define UNVISITED 0
#define VISITED 1
#define EXPLORED 2
typedef struct graphInfo {
int color[MAXN];
int pred[MAXN];
int d[MAXN];
int f[MAXN];
int time;
int N;
} graphInfo;
void DFSAUX(int graph[MAXN][MAXN], struct graphInfo *info, int u, int color) {
int v;
info->color[u] = VISITED;
info->d[u] = info->time++;
for(v = 0; v < info->N; v++){
if (graph[u][v] == 1 && info->color[v] == 0) {
info->pred[v] = u;
DFSAUX(graph, info, v, color == EXPLORED? 3 : EXPLORED);
}
}
info->color[u] = color;
info->f[u] = info->time++;
}
void DFS(int graph[MAXN][MAXN], int N) {
struct graphInfo info;
int u,v;
for(u = 0; u < N; u++) {
info.color[u] = UNVISITED;
info.pred[u] = -1;
info.d[u] = -1;
info.f[u] = -1;
}
info.time = 0;
info.N = N;
for(u = 0; u < N; u++) {
if (info.color[u] == 0) {
DFSAUX(graph, &info, u, EXPLORED);
}
}
//Check for odd cicle
for(u = 0; u < N; u++) {
for (v = 0; v < N; v++) {
if (graph[u][v] == 1 && info.color[u] == info.color[v]) {
printf("NAO\n");
return;
}
}
}
printf("SIM\n");
}
int main(int argc, char** argv) {
int N, M, u, v, k;
int graph[MAXN][MAXN];
char string[500];
char * token;
/*Reads number vertices */
fgets(string, sizeof(string), stdin);
sscanf(string, "%d", &N);
while(N != 0){
/* Initialize graph matrix */
for (u=0; u < N; u++)
for (v=0; v < N; v++)
graph[u][v] = 0;
for (k=0; k < N; k++) {
/* Reads vertex */
fgets(string, sizeof(string), stdin);
sscanf(string, "%d", &u);
/* Reads list of vertices adjacent to vertex i */
fgets(string, sizeof(string), stdin);
token = strtok(string," ");
while (token != NULL){
v = atoi(token);
graph[u-1][v-1] = graph[v-1][u-1] = 1;
token = strtok(NULL," ");
}
}
DFS(graph, N);
/* Reads number of vertices. */
fgets(string, sizeof(string), stdin);
sscanf(string, "%d", &N);
}
}
