Company Organization

You are organizing your company into groups, one group per project. You plan to form $n$ groups. Let $X_i$ (for $i = 1, \dots, n$) be the set of employees assigned to the $i$-th group.

You have a list of requirements about how these groups relate to one another. Each requirement is one of the following five types, applied to a pair of distinct groups $i$ and $j$:

1. $X_i \subseteq X_j$ — group $i$ must be a subset of group $j$.
2. $X_i = X_j$ — the two groups must contain exactly the same employees.
3. $X_i \neq X_j$ — the two groups must not be exactly the same.
4. $X_i \cap X_j = \emptyset$ — the two groups must share no employee.
5. $X_i \cap X_j \neq \emptyset$ — the two groups must share at least one employee.

You may assign any employee to any group, you may hire or fire as many employees as you like, and a group may be empty. The ability of employees is irrelevant.

The requirements were collected without checking for consistency, so it may be impossible to satisfy all of them. Each requirement therefore has a priority, and they are listed from highest to lowest priority. You want to know how many of the highest-priority requirements can be satisfied at the same time — that is, the largest $k$ such that the first $k$ requirements (the $k$ highest-priority ones) can all hold simultaneously.

For example, suppose there are three groups with the following five requirements, listed from highest to lowest priority:

1. $X_2 \subseteq X_1$
2. $X_3 \subseteq X_2$
3. $X_1 \subseteq X_3$
4. $X_1 \neq X_3$
5. $X_3 \subseteq X_1$

Assigning the same set of employees to $X_1$, $X_2$, and $X_3$ satisfies the first three requirements. However, no assignment can satisfy the first four highest-priority requirements at once. Although the first three requirements together with the fifth are satisfiable, the answer is $3$, because only an unbroken prefix of the priority list counts.

The input contains several datasets.

The first line of a dataset contains two integers $n$ and $m$ ($2 \le n \le 100$, $1 \le m \le 10000$): the number of groups and the number of requirements.

Each of the next $m$ lines describes one requirement with three integers $s$, $i$, and $j$ ($1 \le s \le 5$, $1 \le i \le n$, $1 \le j \le n$, $j \neq i$): a requirement of type $s$ (numbered as above) between group $i$ and group $j$. The requirements are given in descending order of priority.

The input ends with a line containing two zeros.

For each dataset, output on its own line the maximum number of highest-priority requirements that can be satisfied simultaneously (the largest $k$ such that the first $k$ requirements are all satisfiable at once).