P7320 「PMOI-4」可怜的团主

lnlhm 被塞给了一张 $n$ 个点 $m$ 条边的**简单无向连通**图。很快，他就被 ducati 和 b6e0 盯上了。 ducati 希望能够从中找到**恰好** $\left \lceil \frac n 6 \right \rceil$ 条**不同**的路径，使得所有的点都被至少一条路径经过。 b6e0 希望找到一个大小**恰好**为 $\lfloor \frac n 3 \rfloor$ 的节点集合，使得它们之间**两两没有边**。 lnlhm 知道，如果他没有满足某个人的要求，那么他就会被揍。因此，他向你求助：是否存在一种选择边或点的方案，使得**最多被一个人揍**？

无

无

【样例解释】 对于第一组样例，我们只需要为 b6e0 选出节点集合 $\{1,4\}$ 即可。注意，$\{1,5\}\{1,6\}\{2,4\}\{2,6\}\{3,4\}\{3,5\}\{3,6\}$ 同样合法。 对于第二组样例，我们只需要为 ducati 选出路径 $1 \to 2 \to 3 \to 4 \to 5 \to 6$ 即可。 【数据范围】 **本题采用捆绑测试**。 - Subtask 1（20pts）：$n,m\le10$。 - Subtask 2（20pts）：保证图为一棵树。 - Subtask 3（60pts）：无特殊限制。 对于 $100\%$ 的数据满足，$3\le n\le10^3$，$3\le m\le\dfrac{n(n-1)}2$，保证给定的图为简单无向连通图。 **温馨提示: 输入量较大，请使用较快的读入方式。**