分数: 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