/*
 *  relations.c
 *  CSCE 235, spring 2007
 *  Brian Kell <bkell@cse.unl.edu>
 */

#include <stdio.h>
#include <stdlib.h>

/* simulate a 2-dimensional matrix with a single-dimensional array; this is a
   trick so I don't have to go through a bunch of loops to malloc everything */
#define R(a,b)  r[(a)*s+(b)]

int main(void)
{
	/* s : cardinality of set
	   n : number of ordered pairs in the relation
	   r : matrix
	   i : loop index
	   a, b, c : represent elements of the set      */
	int s, n, *r, i, a, b, c;

	/* continue looping until we explicitly exit */
	while (1)
	{
		/* read first two integers in input */
		if (scanf("%d%d", &s, &n) != 2)  exit(EXIT_FAILURE);
		/* if first integer is 0, exit */
		if (s == 0)  exit(EXIT_SUCCESS);

		/* allocate matrix, initialize to zero */
		r = calloc((size_t)(s*s), sizeof(int));
		if (r == 0)  exit(EXIT_FAILURE);

		/* read all the pairs of the relation */
		for (i = 0; i < n; ++i) {
			if (scanf("%d%d", &a, &b) != 2)  exit(EXIT_FAILURE);
			/* put a 1 in the appropriate place in the matrix */
			R(a-1,b-1) = 1;
		}

		/* check for reflexivity */
		for (a = 0; a < s; ++a)
			if (!R(a,a)) {
				/* if some element in the set is not related to itself, then we
				   know the relation is not reflexive, so output this and jump
				   to symmetry testing */
				printf("not reflexive, ");
				goto CHECK_SYM;
			}
		/* if we got this far the relation is reflexive */
		printf("reflexive, ");

CHECK_SYM:
		/* check for symmetry */
		for (a = 0; a < s; ++a)
			for (b = 0; b < s; ++b)
				if (R(a,b) && !R(b,a)) {
					/* if there exist a, b in the set such that a is related
					   to b but b is not related to a, then we know the
					   relation is not symmetric, so output this and jump to
					   transitivity testing */
					printf("not symmetric, ");
					goto CHECK_TRANS;
				}
		/* if we got this far the relation is symmetric */
		printf("symmetric, ");

CHECK_TRANS:
		/* transitivity testing */
		for (a = 0; a < s; ++a)
			for (b = 0; b < s; ++b)
				/* only consider this choice of a and b if a is related to b */
				if (R(a,b))
					for (c = 0; c < s; ++c)
						if (R(b,c) && !R(a,c)) {
							/* if there exist a, b, c in the set such that a is
							   related to b and b is related to c, but a is not
							   related to c, then we know the relation is not
							   transitive, so output this and jump to end */
							printf("not transitive\n");
							goto END_CHECKS;
						}
		/* if we got this far the relation is transitive */
		printf("transitive\n");

END_CHECKS:
		/* deallocate matrix */
		free(r);
	}

	return 0;
}