F - 一触即発 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 7 点

注意

この問題に対する言及は、2020/12/27 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

薬品が N 種類あり、薬品 1 から薬品 N まで番号付けされています。あなたは、これらのうち 1 種類以上を選んで混ぜ、新たな物質を作ります。
これらの薬品は危険なため、混ぜ方によっては爆発することがあります。
1 \le i \le M を満たす整数 i が存在して、薬品 A_i, B_i, C_i の 3 種類の薬品が全て混ぜられているとき、爆発します。それ以外の場合には爆発しません。
あなたは痛い目を見たくないので、直ちに爆発するような混ぜ方はしません。しかし、できる限り爆発寸前の物質を作りたいので、「物質に薬品 x を新たに追加すると爆発するような薬品 x の数」をできる限り大きくしようとします。
この数として考えられる最大の値を求めてください。

制約

  • 3 \le N \le 14
  • 1 \le M \le \frac{N(N - 1)(N - 2)}{6}
  • 1 \le A_i \lt B_i \lt C_i \le N
  • (A_i, B_i, C_i) \neq (A_j, B_j, C_j) (i \neq j)
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1 C_1
A_2 B_2 C_2
A_3 B_3 C_3
\hspace{25pt} \vdots
A_M B_M C_M

出力

作る物質に新たに追加すると爆発するような薬品の数として考えられる最大値を出力せよ。

入力例 1

4 2
1 2 3
1 2 4

出力例 1

2

薬品 1 と薬品 2 を選んで混ぜると、直ちに爆発はせず、薬品 3, 4 のどちらを追加しても爆発するので、「物質に新たに追加すると爆発するような薬品の種類数」 が 2 となります。
この数をこれより大きくすることはできないので答えは 2 です。

入力例 2

6 7
1 2 5
2 3 5
2 4 5
1 2 3
4 5 6
2 5 6
1 3 5

出力例 2

4

薬品 2 と薬品 5 を選んで混ぜると、薬品 1, 3, 4, 6 全てが「新たに追加すると爆発するような薬品」となります。

入力例 3

5 1
1 2 3

出力例 3

1

Score : 7 points

Warning

Do not make any mention of this problem until December 27, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have N chemicals, labeled Chemical 1 through Chemical N. You will choose one or more of these chemicals and mix them to make a new substance.
These dangerous chemicals can explode if mixed wrongly.
More specifically, if there is an integer i (1 \le i \le M) such that the chemicals A_i, B_i, and C_i are all used in the mixture, they will explode; otherwise, no explosion happens.
You will not mix chemicals in a way that results in an immediate explosion, which hurts. However, you do want to make a substance that is as close to an explosion as possible, so you want to make the following count as large as possible: the number of chemicals x that results in an explosion if Chemical x is added to the substance.
Find the maximum possible value of this count.

Constraints

  • 3 \le N \le 14
  • 1 \le M \le \frac{N(N - 1)(N - 2)}{6}
  • 1 \le A_i \lt B_i \lt C_i \le N
  • (A_i, B_i, C_i) \neq (A_j, B_j, C_j) (i \neq j)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1 C_1
A_2 B_2 C_2
A_3 B_3 C_3
\hspace{25pt} \vdots
A_M B_M C_M

Output

Print the maximum possible number of chemicals x that results in an explosion if Chemical x is added to the substance you make.

Sample Input 1

4 2
1 2 3
1 2 4

Sample Output 1

2

If we choose Chemical 1 and 2 and mix them, they do not immediately explode, but adding either Chemical 3 or 4 results in an explosion, which means the count in question is 2.
It is impossible to make this count larger, so the answer is 2.

Sample Input 2

6 7
1 2 5
2 3 5
2 4 5
1 2 3
4 5 6
2 5 6
1 3 5

Sample Output 2

4

If we choose Chemical 2 and 5, adding any one of Chemicals 1, 3, 4, and 6 results in an explosion.

Sample Input 3

5 1
1 2 3

Sample Output 3

1