你在几年前创办了一家公司，幸运的是，它非常成功。随着公司的发展，你发现需要以更有组织的方式管理员工，并决定成立几个小组并将员工分配给他们。

现在，你计划成立 $n$ 个小组，每个小组对应公司的一个项目。有时，你对小组中的成员有一些限制。例如，一个小组必须是另一个小组的子集，因为前一个小组将由后一个小组的高级成员组成；两个小组的成员必须完全相同，因为这两个项目当前的活动密切相关；两个小组的成员不能完全相同，以防止腐败；由于安全原因，两个小组不能有共同的员工；为了促进合作，两个小组必须有共同的员工。

简而言之，令 $X_i$ ($i = 1, \dots, n$) 表示分配给第 $i$ 个小组的员工集合，我们有以下五种类型的限制：

1. $X_i \subseteq X_j$
2. $X_i = X_j$
3. $X_i \neq X_j$
4. $X_i \cap X_j = \emptyset$
5. $X_i \cap X_j \neq \emptyset$

由于你在列出这些限制时没有考虑一致性，因此可能无法同时满足所有限制。因此，限制是按照优先级顺序排列的，现在你想知道最多可以同时满足多少个优先级最高的限制（即最大前缀数量）。

你不需要考虑员工的能力。也就是说，你可以将任何人分配给任何小组。此外，你也可以创建没有员工的小组。如果你可以通过雇用或解雇任意数量的员工来满足更多限制，你可以这样做。

例如，假设我们对三个小组有以下五个限制，按优先级从高到低排列，对应样例输入中的第一个数据集：

• $X_2 \subseteq X_1$
• $X_3 \subseteq X_2$
• $X_1 \subseteq X_3$
• $X_1 \neq X_3$
• $X_3 \subseteq X_1$

通过将相同的员工集合分配给 $X_1, X_2$ 和 $X_3$，我们可以满足前三个限制。然而，无论我们如何将员工分配给 $X_1, X_2$ 和 $X_3$，我们都无法同时满足前四个最高优先级的限制。虽然我们可以同时满足前三个限制和第五个限制，但答案应该是 $3$。

输入格式

输入包含多个数据集。

每个数据集的第一行包含两个整数 $n$ ($2 \le n \le 100$) 和 $m$ ($1 \le m \le 10000$)，分别表示小组的数量和限制的数量。

接下来是 $m$ 行，每行描述一个限制。每个限制的描述包含三个整数 $s$ ($1 \le s \le 5$)、$i$ ($1 \le i \le n$) 和 $j$ ($1 \le j \le n, j \neq i$)，表示对第 $i$ 个小组和第 $j$ 个小组施加的第 $s$ 种类型的限制。限制的类型编号如上所述。限制按优先级从高到低的顺序给出。

输入以包含两个零的一行结束。

输出格式

对于每个数据集，输出一个整数，表示可以同时满足的最高优先级限制的最大数量。

样例

输入样例 1

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

输出样例 1

3
4
4
2