AT_past202012_f 一触即発

有 $N$ 种药品，编号为 $1$ 到 $N$。你可以从中选择至少一种药品进行混合，制造出一种新物质。 这些药品具有危险性，某些混合方式会导致爆炸。 存在整数 $i$ 满足 $1 \leq i \leq M$，如果药品 $A_i$、$B_i$、$C_i$ 这三种药品全部被混合，则会发生爆炸。除此之外的混合方式不会爆炸。 你不想让混合物立即爆炸，但又希望尽可能制造出“接近爆炸”的物质，即你希望“向当前物质中再加入一种药品就会爆炸的药品种类数”尽可能多。 请你求出，这个数的最大可能值。

输入通过标准输入给出，格式如下： > $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$

输出一个整数，表示“向当前物质中再加入一种药品就会爆炸的药品种类数”的最大可能值。

### 注意 本题在 2020 年 12 月 27 日 18:00（日本标准时间）前禁止公开讨论。若有讨论，可能会被追究责任。考试结束后可以公开总分和认证等级，但请不要透露解答了哪些题目等信息。 ### 约束条件 - $3 \leq N \leq 14$ - $1 \leq M \leq \frac{N(N-1)(N-2)}{6}$ - $1 \leq A_i < B_i < C_i \leq N$ - $(A_i, B_i, C_i) \neq (A_j, B_j, C_j)\ (i \neq j)$ - 所有输入均为整数 ### 样例解释 1 如果选择药品 $1$ 和药品 $2$ 混合，不会立即爆炸，但无论再加入药品 $3$ 还是 $4$，都会爆炸，因此“向当前物质中再加入一种药品就会爆炸的药品种类数”为 $2$。无法使这个数更大，所以答案为 $2$。 ### 样例解释 2 如果选择药品 $2$ 和药品 $5$ 混合，则药品 $1$、$3$、$4$、$6$ 都属于“再加入就会爆炸的药品”，所以答案为 $4$。 由 ChatGPT 4.1 翻译