← 返回题目列表

AtCoder · past202012_f

F. 危险化学品

中文机器翻译题面 查看原题

分数: 7 点

警告

2020 年 12 月 27 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

我们有 N 化学品,标记为化学品 1 通过化学 N。您将选择一种或多种化学物质并将它们混合以制造新物质。
这些危险化学品如果混合不当可能会爆炸。
更具体地说,如果有一个整数 i (1 \le i \le M) 使得化学品 A_i, B_i,和 C_i 全部用在混合物中,它们会爆炸;否则不会发生爆炸。
您不会以导致立即爆炸的方式混合化学品,这会造成伤害。但是,您确实希望制造一种尽可能接近爆炸的物质,因此您希望使以下计数尽可能大:化学品的数量 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

输出

打印最大可能的化学品数量 x 如果化学物质会导致爆炸 将 x 添加到您制造的物质中。


示例输入 1

4 2
1 2 3
1 2 4

示例输出 1

2

如果我们选择化工 1 和 2 并混合它们,它们不会立即爆炸,但添加任一化学物质 3 or 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