P6853 station

你需要规划一个城市的公交路线。 总共有 $n$ 条路线和 $m$ 个车站，编号均从 $1$ 开始。 你的主要任务是，规划每一条路线应该经过哪些车站。换言之，你要任意选择一个车站的子集，让这条路线经过这个子集中的所有车站。 定义两条路线是**关联**的，当且仅当它们经过了同一个车站，也就是它们的经过车站集合有交。 一个路线方案必须满足如下限制： 1. 一条线路不可能只通过一个车站，所以**每条线路至少要经过两个车站**； 2. 一个车站的运载能力是有限的，所以**一个车站最多只能被三条线路经过**。 3. 为了保证交通顺畅，对于任意两条不同线路 $i, j(i \not = j)$，都存在第三条线路 $k (k \not = i, k \not = j)$，使得 $k$ 与 $i, j$ 均**关联**。 现给定 $n$，请求出一个最小的 $m$ 和具体规划方案。

无

无

#### 「样例 1 解释」 如图所示。  首先易知其满足题目描述中所给定的一、二条件。下面考虑三条件。 先考虑 $1, 2, 4$ 号线，可以发现这三条线路构成了一个三角形，任意两个线路均有剩下的一条线路与它们**关联**； 再对 $3$ 号线与 $1, 2, 4$ 号线分别考虑，容易验证满足对于任意 $x \in \{1, 2, 4\}$，均有另一条线路 $y \in \{1, 2, 4\}, y \not = x$ 与 $3, x$ 同时**关联**，满足题目条件。 --- #### 「Special Judge 说明与评分细则」 **请认真阅读输出格式**。 如果你的输出出现了如下情况，将会被判为 $0$ 分： - 输出格式不符。如没有正确换行，输出了一些奇奇怪怪的字符，未输出车站个数等。 - 某一条线路经过了相同的车站，或者有某一个车站的编号不在 $[1, m]$ 内。 - 没有满足题目描述中所给定的三条限制。 - 输出文件大小过大或者是 $m$ 过大。如果你的 $m$ 大于 $10 ^6$ 将直接判为 $0$ 分。输出文件过大将导致 TLE 或 OLE，建议将输出文件大小控制在 25Mb 以内。 在没有被判为 $0$ 分的基础上，将会根据你输出的 $m$ 的大小进行判分。 每个测试点评测时会有 $10$ 个评测参数 $w _1, w _2, \cdots, w _{10}$，若你输出的 $m$ 小于等于其中 $k$ 个参数，那么你将得到该测试点 $k \times 10\%$ 的分数。 这 $10$ 个参数是对外不可见的，也即你的程序在运行时无法获知这些评测参数。 --- #### 「数据范围」 **本题采用捆绑测试**。你在某个 subtask 的得分为在**该 subtask 的所有测试点中的最小得分**。 - Subtask 1(20 points)：$n \le 10$。此处我们保证 $10$ 个评分参数均为 $10 ^6$。 - Subtask 2(40 points)：$n \le 200$。 - Subtask 3(40 points)：无特殊限制。 对于所有数据，均满足 $3 \le n \le 4 \times 10 ^3$，且 $ans + 5 \le w _1 \le w _2 \le \cdots \le w _{10} = 10 ^6$，其中 $ans$ 表示标准答案。 请注意此处的 $w _{10} = 10^6$ 的条件。