회사 조직 구성

문제

회사를 프로젝트별로 하나씩, 총 $n$개의 그룹으로 나누어 조직하려고 합니다. $i$번째 그룹에 배정된 직원의 집합을 $X_i$ ($i = 1, \dots, n$)라고 합시다.

그룹들 사이의 관계에 대한 요구 사항 목록이 있습니다. 각 요구 사항은 서로 다른 두 그룹 $i$와 $j$에 대해 다음 다섯 가지 유형 중 하나입니다.

$X_i \subseteq X_j$ — 그룹 $i$는 그룹 $j$의 부분집합이어야 합니다.
$X_i = X_j$ — 두 그룹의 직원이 완전히 같아야 합니다.
$X_i \neq X_j$ — 두 그룹이 완전히 같아서는 안 됩니다.
$X_i \cap X_j = \emptyset$ — 두 그룹은 공통 직원을 가지지 않아야 합니다.
$X_i \cap X_j \neq \emptyset$ — 두 그룹은 적어도 한 명의 공통 직원을 가져야 합니다.

어떤 직원이든 어떤 그룹에나 배정할 수 있고, 원하는 만큼 직원을 채용하거나 해고할 수 있으며, 빈 그룹이 있어도 됩니다. 직원의 능력은 고려하지 않습니다.

요구 사항은 일관성을 확인하지 않고 수집되었기 때문에 모두 만족시키는 것이 불가능할 수 있습니다. 그래서 각 요구 사항에는 우선순위가 있으며, 우선순위가 높은 것부터 낮은 순서로 나열되어 있습니다. 우선순위가 가장 높은 요구 사항들을 동시에 몇 개까지 만족시킬 수 있는지, 즉 처음 $k$개(우선순위가 가장 높은 $k$개)의 요구 사항을 모두 동시에 만족시킬 수 있는 최대 $k$를 구하세요.

예를 들어 세 개의 그룹에 대해 우선순위가 높은 것부터 낮은 순서로 다음 다섯 개의 요구 사항이 있다고 합시다.

$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$에 같은 직원 집합을 배정하면 처음 세 요구 사항을 만족시킬 수 있습니다. 하지만 어떤 배정으로도 우선순위가 높은 처음 네 개의 요구 사항을 동시에 만족시킬 수는 없습니다. 처음 세 요구 사항과 다섯 번째 요구 사항을 함께 만족시킬 수는 있지만, 우선순위 목록의 끊기지 않은 앞부분만 인정되므로 정답은 $3$입니다.

입력

입력은 여러 개의 데이터셋으로 이루어져 있습니다.

각 데이터셋의 첫 줄에는 두 정수 $n$과 $m$ ($2 \le n \le 100$, $1 \le m \le 10000$)이 주어집니다. 각각 그룹의 수와 요구 사항의 수입니다.

이어지는 $m$개의 줄에는 각각 하나의 요구 사항이 세 정수 $s$, $i$, $j$ ($1 \le s \le 5$, $1 \le i \le n$, $1 \le j \le n$, $j \neq i$)로 주어집니다. 이는 그룹 $i$와 그룹 $j$ 사이의 유형 $s$(위 번호와 같음) 요구 사항을 의미합니다. 요구 사항은 우선순위가 높은 순서대로 주어집니다.

입력의 끝은 두 개의 0이 적힌 줄로 표시됩니다.

출력

각 데이터셋에 대해, 동시에 만족시킬 수 있는 우선순위가 가장 높은 요구 사항의 최대 개수(처음 $k$개의 요구 사항을 모두 동시에 만족시킬 수 있는 최대 $k$)를 한 줄에 하나씩 출력하세요.