Company Organization#5419
You started a company a few years ago, and fortunately, it has been highly successful. As your company grew, you noticed the need to manage employees in a more organized way and decided to form several groups and assign employees to them.
Now, you are planning to form groups, each of which corresponds to a project in the company. Sometimes, there are constraints regarding the membership of these groups. For example: - A group must be a subset of another group because it consists of senior members of the latter, - The members in two groups must be exactly the same because their projects are closely related, - The members in two groups must not be exactly the same to avoid corruption, - Two groups cannot have any common employee due to security reasons, - Two groups must have at least one common employee to facilitate collaboration.
Let X_i (i = 1, \ldots, n) denote the set of employees assigned to the -th group. There are five types of constraints given as follows:
1. X_i \subseteq X_j 2. X_i = X_j 3. X_i \neq X_j 4. X_i \cap X_j = \varnothing 5. X_i \cap X_j \neq \varnothing
Since the constraints are listed without considering consistency, it might be impossible to satisfy all of them simultaneously. The constraints are ordered according to their priorities. Your task is to determine the largest prefix of the constraints (starting from the highest priority) that can be satisfied at the same time.
You do not have to consider the abilities of employees. That is, you can assign anyone to any group, and you may form groups with no employees. Furthermore, you may hire or fire as many employees as needed to satisfy more constraints.
For example, suppose that the following five constraints on three groups are given in order of priority (corresponding to the first dataset in the sample input):
- 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
By assigning the same set of employees to X_1, X_2, and X_3, the first three constraints can be satisfied. However, it is impossible to satisfy the first four highest-priority constraints simultaneously. Although the first three constraints and the fifth constraint can be satisfied at the same time, the answer should be three.
The input consists of several datasets. The first line of each dataset contains two integers (2 \le n \le 100) and (1 \le m \le 10000), the number of groups and the number of constraints, respectively. The next lines describe the constraints. Each constraint is given as three integers (1 \le s \le 5), (1 \le i \le n), and (1 \le j \le n,\ j \neq i), indicating a constraint of the -th type applied to the -th and -th groups, as listed above. The constraints are provided in descending order of priority.
The input ends with a line containing two zeros.
For each dataset, output the number of highest-priority constraints that can be satisfied simultaneously.
Example 1