{"raw_statement":[{"iden":"background","content":"[![](https://cdn.luogu.com.cn/upload/image_hosting/inglwsjz.png)](https://music.163.com/#/program?id=2067229684)\n\n为什么评级 7？\n\nPowerless：Equilibrium FTR 9."},{"iden":"statement","content":"小机器人又在钓星星了。\n\n星星在天空中形成了若干个星座，每个星座有一个“中心点”，如果星星脱离了与中心点的直接或间接的联系，那么星星就会从星座中脱离，掉落到地面上。\n\n经过小机器人日日夜夜的观测，他发现了这些星座的性质：每一个星座内部都是联通的，星星的联系的数量总与星座中星星的数量相等。\n\n另外，不同的星座之间星星没有联系，同一个星座中的星星都有间接或直接的联系。\n\n他通过观测天体运动给星星编了号，他发现每个星座的中心点都是星座中编号最小的星星。\n\n可惜的是，小机器人只能通过随（diao）缘（yu）的方式获得取消这些联系的钥匙。\n\n小机器人非常贪心，想要用尽量少的时间获得尽量多的星星。\n\n他想要 $k$ 颗星星，你能告诉他他至少需要钓上几把钥匙吗？\n\n如果你解决了这个问题，说不定小机器人会送给你几颗星星哦~\n\n**[简化题意](https://www.luogu.com.cn/paste/5nhqqjzm)**"},{"iden":"input","content":"第一行两个整数 $n,k$，表示**天空中**所有的星星的**总数**和星星之间联系**总数**，和小机器人希望获得的星星数。\n\n接下来 $n$ 行，每行两个整数 $u,v$ 表示 第 $u$ 颗和第 $v$ 颗星星之间存在联系。\n\n保证任意星座内星星联系条数等于星星数，星星不会有自己到自己的联系，不会有两条联系建立在同样两颗星星上。"},{"iden":"output","content":"一行一个整数，表示小机器人需要获得足够的星星所需最少的钥匙数。"},{"iden":"note","content":"**本题采用捆绑测试。**\n\n设星座共有 $l$ 个。\n\n对于 $100\\%$ 的数据，保证 $1\\le n\\le 10^6,1\\le k\\le n-l$。\n\nSubtask 1：对于 $20\\%$ 的数据，保证 $n\\le 1000$。\n\nSubtask 2：对于 $10\\%$ 的数据，保证 $l\\le 5$。\n\nSubtask 3：对于 $20\\%$ 的数据，保证 $l\\le 15$。\n\nSubtask 4：无特殊限制。\n\n----\n\n样例解释 $1$：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/ov9db62k.png)\n\n消除 $(1,4)$ 间联系即可。\n\n样例解释 $2$：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/wh22obzj.png)\n\n消除 $(8,14),(8,10),(8,16)$ 三条联系即可。\n\n可以证明没有消除联系更少的方法。\n\n可能有别的方法也仅需要消除 $3$ 条联系。"}],"translated_statement":null,"sample_group":[["4 1\n1 2\n2 3\n3 1\n1 4","1"],["17 9\n1 2\n1 6\n1 3\n3 4\n4 5\n5 6\n6 7\n8 10\n10 9\n10 11\n11 12\n11 13\n13 14\n14 8\n15 13\n8 16\n16 17","3"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}