{"raw_statement":[{"iden":"background","content":"在著名的生命游戏中，二维方格中每个细胞死或活的状态由它周围的八个细胞（上、下、左、右、左上、左下、右上、右下）所决定。\n\n具体规则如下：\n\n孤单死亡：如果细胞的邻居小于等于 1 个，则该细胞在下一次状态将死亡；\n\n拥挤死亡：如果细胞的邻居在 4 个及以上，则该细胞在下一次状态将死亡；\n\n稳定：如果细胞的邻居为 2 个或 3 个，则下一次状态为稳定存活；\n\n复活：如果某位置原无细胞存活，而该位置的邻居为 3 个，则该位置将复活一个细胞。\n\n在此规则下也出现了很多有趣的图形，比如说下图就是\"轻量级飞船\"连续的五个回合的情况：它的周期是 4，每 2 个回合会向右边走一格。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/28o5txyh.png)"},{"iden":"statement","content":"现在我们将在树上进行简化版的生命游戏，首先将给出一棵含有 $n$ 个点，$n-1$ 条边的树和一个整数 $k$。\n\n在每回合时，当前剩余的度数为 $k$ 的点及与其连接的边会瞬间同时被删去。\n\n形式化的，每回合都将按顺序进行如下操作：\n\n   -  统计当前剩余每个点的度数（一个点的度数定义为为，这个点当前连接的边的条数）。\n   - 将所有度数**恰好**为 $k$ 的点标记。\n   - 将上一步标记的点及其连接的边全部删去。\n\n我们希望知道在无穷多回合后，这棵树将被分为多少个连通块。若最终两个点能够直接或间接的通过若干条边相连，则认为这两个点属于同一个连通块。"},{"iden":"input","content":"第一行两个整数 $n,k$ ($0\\le k < n \\le 10^6$)，用空格隔开。\n\n接下来 $n-1$ 行，每行两个用空格隔开的正整数 $u_i,v_i$ ($1\\le u_i, v_i \\le n$) 表示 $u_i$ 和 $v_i$ 之间有一条边。\n\n输入的数据量较大，建议使用快速的读入方式。"},{"iden":"output","content":"共一行一个整数，表示无穷多回合之后剩余的连通块个数。\n"},{"iden":"note","content":"\n对于样例 1:\n\n这棵树的初始形态为：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/g5x6u2fx.png)\n\n其中三个点的度数依次为 $1,2,1$。\n\n在一回合过后，点 $1,3$ 被删除。\n\n这棵树变为：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/5x6vo3it.png)\n\n容易发现之后这棵树的形态将不会变化，所以最终的连通块个数是 $1$。\n\n对于样例 2：\n\n初始形态为：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/hdq30nrf.png)\n\n一回合之后变为：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/td8lj616.png)\n\n之后保持不变，最终连通块个数为 $2$。\n\n对于样例 3：\n\n初始形态：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/tfu21fc0.png)\n\n一回合之后变为：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/3ad1bwnz.png)\n\n再过一回合之后变为：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/2ax9h1tt.png)\n\n之后保持不变，最终连通块个数为 $5$。"}],"translated_statement":null,"sample_group":[["3 1\n1 2\n2 3\n","1\n"],["4 2\n1 2\n2 3\n3 4\n","2\n"],["10 3\n1 2\n2 3\n9 4\n3 5\n5 6\n6 7\n3 9\n5 8\n5 10\n","5\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}