{"raw_statement":[{"iden":"statement","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 火星人。现在你需要完成这道题，证明火星人的智慧。"},{"iden":"input","content":"第一行：两个整数 $n,m$，分别表示图 $G$ 的结点数和边数。\n\n接下来 $m$ 行：每行两个整数 $x,y$，表示一条连接结点 $x,y$ 的无向边。"},{"iden":"output","content":"第一行：两个整数 $k_{min},t$，分别表示最小的 $k$ 以及对应的划分大小。\n\n接下来 $t$ 行：第 $i$ 行首先一个整数 $s_i$，表示 $V_i$ 的大小，然后 $s_i$ 个整数表示 $V_i$ 的元素。\n\n如有多种划分方案，可以任意输出一种，注意你并不需要最小化 $t$。"},{"iden":"note","content":"**【样例解释】**\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\n![](https://cdn.luogu.com.cn/upload/image_hosting/41etnpdx.png)"}],"translated_statement":null,"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"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}