{"problem":{"name":"白鹭兰","description":{"content":"有很多有关火星人的传说，比如他们的 DNA 非常复杂，他们有成千上万根手指等等，但这些都没有得到证实。同样没有得到证实的一个传说是火星人很会做 OI 题。 为了验证最后这个传说，地球人们给来自火星的外星旅人出了一道 OI 题： > 给定一张 $n$ 个点 $m$ 条边的无向连通图 $G=(V,E)$，请找出最小的 $k$ 使得存在一个对点集的划分 $V_1,\\ldots,V_t$ 使得： > ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9394"},"statements":[{"statement_type":"Markdown","content":"有很多有关火星人的传说，比如他们的 DNA 非常复杂，他们有成千上万根手指等等，但这些都没有得到证实。同样没有得到证实的一个传说是火星人很会做 OI 题。\n\n为了验证最后这个传说，地球人们给来自火星的外星旅人出了一道 OI 题：\n\n> 给定一张 $n$ 个点 $m$ 条边的无向连通图 $G=(V,E)$，请找出最小的 $k$ 使得存在一个对点集的划分 $V_1,\\ldots,V_t$ 使得：\n>\n> - $\\forall 1\\leq x\\leq t$，$\\bigcup_{i=1}^x V_i$ 的导出子图连通；\n>\n> - $\\forall 1\\leq x\\leq t$，$\\bigcup_{i=x}^t V_i$ 的导出子图连通；\n>\n> - $\\forall 1\\leq x\\leq t$，$|V_x|\\leq k$。\n>\n> 注意，作为划分，还需要满足 $\\bigcup_{i=1}^t V_i=V$，$ V_i\\cap V_j=\\varnothing\\ (\\forall i\\neq j)$，且所有 $V_i$ 非空。\n>\n> 请给出最小的 $k$ 以及对应的划分。\n\n再见，You're 火星人。现在你需要完成这道题，证明火星人的智慧。\n\n## Input\n\n第一行：两个整数 $n,m$，分别表示图 $G$ 的结点数和边数。\n\n接下来 $m$ 行：每行两个整数 $x,y$，表示一条连接结点 $x,y$ 的无向边。\n\n## Output\n\n第一行：两个整数 $k_{min},t$，分别表示最小的 $k$ 以及对应的划分大小。\n\n接下来 $t$ 行：第 $i$ 行首先一个整数 $s_i$，表示 $V_i$ 的大小，然后 $s_i$ 个整数表示 $V_i$ 的元素。\n\n如有多种划分方案，可以任意输出一种，注意你并不需要最小化 $t$。\n\n[samples]\n\n## Note\n\n**【样例解释】**\n\n如下图，$V_1,\\ldots,V_5$ 分别是红色/橙色/绿色/蓝色/紫色点集，可以验证这满足题目条件。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/omc7gvxe.png)\n\n--- \n\n**【评分方式】**\n\n如果你的输出格式错误，将有可能不得分，也可能导致不可预知的错误。\n\n如果你的输出格式正确，若你的 $k_{min}$ 正确，你将获得测试点 $50\\%$ 的分数，若在此基础上你的构造方案正确，你将获得测试点 $100\\%$ 的分数。\n\n---\n\n**【数据范围】**\n\n对于全部数据：$2\\leq n\\leq 2\\times 10^5$，$1\\leq m\\leq 2.3\\times 10^5$，$1\\leq x,y\\leq n$，保证给出的 $m$ 条边中没有重边和自环，保证给出的图连通。\n\n|     子任务编号     | $m\\leq$ |        特殊限制        | 分值 |\n| :----------------: | :-------------: | :--------------------: | :--: |\n| $\\text{Subtask 1}$ |     $2\\times 10^5$     | $G$ 是链 | $10$ |\n| $\\text{Subtask 2}$ |      $10$       |         无          | $10$ |\n| $\\text{Subtask 3}$ |     $2000$      |         $G$ 是树          | $15$ |\n| $\\text{Subtask 4}$ |     $2000$      |         无          | $20$ |\n| $\\text{Subtask 5}$ |      $10^5$      |           $G$ 是树           | $15$ |\n| $\\text{Subtask 6}$ |     $2.3\\times 10^5$     |           无           | $30$ |\n\n---\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/41etnpdx.png)","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9394","tags":["洛谷原创","Special Judge","O2优化","洛谷月赛"],"sample_group":[["7 7\n1 2\n1 3\n1 5\n1 6\n4 5\n5 6\n6 7\n","2 5\n1 2\n2 1 3\n2 5 4\n1 6\n1 7\n"]],"created_at":"2026-03-03 11:09:25"}}