P9394 白鹭兰
题目描述
有很多有关火星人的传说，比如他们的 DNA 非常复杂，他们有成千上万根手指等等，但这些都没有得到证实。同样没有得到证实的一个传说是火星人很会做 OI 题。
为了验证最后这个传说，地球人们给来自火星的外星旅人出了一道 OI 题：
> 给定一张 $n$ 个点 $m$ 条边的无向连通图 $G=(V,E)$，请找出最小的 $k$ 使得存在一个对点集的划分 $V_1,\ldots,V_t$ 使得：
>
> - $\forall 1\leq x\leq t$，$\bigcup_{i=1}^x V_i$ 的导出子图连通；
>
> - $\forall 1\leq x\leq t$，$\bigcup_{i=x}^t V_i$ 的导出子图连通；
>
> - $\forall 1\leq x\leq t$，$|V_x|\leq k$。
>
> 注意，作为划分，还需要满足 $\bigcup_{i=1}^t V_i=V$，$ V_i\cap V_j=\varnothing\ (\forall i\neq j)$，且所有 $V_i$ 非空。
>
> 请给出最小的 $k$ 以及对应的划分。
再见，You're 火星人。现在你需要完成这道题，证明火星人的智慧。
输入格式
无
输出格式
无
说明/提示
**【样例解释】**
如下图，$V_1,\ldots,V_5$ 分别是红色/橙色/绿色/蓝色/紫色点集，可以验证这满足题目条件。
---
**【评分方式】**
如果你的输出格式错误，将有可能不得分，也可能导致不可预知的错误。
如果你的输出格式正确，若你的 $k_{min}$ 正确，你将获得测试点 $50\%$ 的分数，若在此基础上你的构造方案正确，你将获得测试点 $100\%$ 的分数。
---
**【数据范围】**
对于全部数据：$2\leq n\leq 2\times 10^5$，$1\leq m\leq 2.3\times 10^5$，$1\leq x,y\leq n$，保证给出的 $m$ 条边中没有重边和自环，保证给出的图连通。
| 子任务编号 | $m\leq$ | 特殊限制 | 分值 |
| :----------------: | :-------------: | :--------------------: | :--: |
| $\text{Subtask 1}$ | $2\times 10^5$ | $G$ 是链 | $10$ |
| $\text{Subtask 2}$ | $10$ | 无 | $10$ |
| $\text{Subtask 3}$ | $2000$ | $G$ 是树 | $15$ |
| $\text{Subtask 4}$ | $2000$ | 无 | $20$ |
| $\text{Subtask 5}$ | $10^5$ | $G$ 是树 | $15$ |
| $\text{Subtask 6}$ | $2.3\times 10^5$ | 无 | $30$ |
---
