{"problem":{"name":"[USACO23DEC] A Graph Problem P","description":{"content":"为了丰富自己的数学知识，Bessie 选修了一门图论课程，她发现她被下面的问题困住了，请帮帮她！ 给出一张连通的无向图，包含编号为 $1\\dots N$ 的节点和编号为 $1\\dots M$（$2 \\le N \\le 2\\cdot 10^5$，$N - 1 \\le M \\le 4 \\cdot 10^5$）的边，下边的操作将被实施： 1. 假设集合 $S=\\{v\\}$，变量 $h=0$。 2. ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9984"},"statements":[{"statement_type":"Markdown","content":"为了丰富自己的数学知识，Bessie 选修了一门图论课程，她发现她被下面的问题困住了，请帮帮她！\n\n给出一张连通的无向图，包含编号为 $1\\dots N$ 的节点和编号为 $1\\dots M$（$2 \\le N \\le 2\\cdot 10^5$，$N - 1 \\le M \\le 4 \\cdot 10^5$）的边，下边的操作将被实施：\n\n1. 假设集合 $S=\\{v\\}$，变量 $h=0$。\n2. 当 $|S|<N$，重复执行：\n\t1. 仅有一个顶点在集合 $S$ 中的边中，找到编号最小的那条，编号记为 $e$。\n    2. 将 $e$ 不在 $S$ 中的那个顶点加入集合 $S$。\n    3. 将 $h$ 修改为 $10h+e$。\n3. 返回 $h$ 对 $10^9+7$ 取模的值。\n\n输出这个过程的全部返回值。\n\n## Input\n\n第一行包含 $N$ 和 $M$。接下来 $M$ 行，每行包含第 $e$ 条边的顶点 $(a_e,b_e)$，保证图连通，没有重边。\n\n## Output\n\n输出 $N$ 行，第 $i$ 行包含在节点 $i$ 开始过程的返回值。\n\n[samples]\n\n## Note\n\n### 样例解释 2\n\n考虑在 $i=3$ 开始执行。首先，选择 $2$ 号边，$S=\\{3,4\\}$，$h=2$。然后，选择 $3$ 号边，$S=\\{2,3,4\\}$，$h=23$。接着，选择 $1$ 号边，$S=\\{1,2,3,4\\}$，$h=231$。最后，选择 $5$ 号边，$S=\\{1,2,3,4,5\\}$，$h=2315$。因此，$i=3$ 的答案是 $2315$。\n\n### 样例解释 3\n\n确保答案对 $10^9+7$ 取模。\n\n### 测试点性质\n\n- 测试点 $4$ 满足 $N,M \\le 2000$。\n- 测试点 $5-6$ 满足 $N \\le 2000$。\n- 测试点 $7-10$ 满足 $N \\le 10000$。\n- 测试点 $11-14$ 满足对于所有边，有 $a_e+1=b_e$。\n- 测试点 $15-23$ 没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9984","tags":["线段树","USACO","并查集","2023","Kruskal 重构树","O2优化","哈希 hashing","启发式合并"],"sample_group":[["3 2\n1 2\n2 3","12\n12\n21"],["5 6\n1 2\n3 4\n2 4\n2 3\n2 5\n1 5","1325\n1325\n2315\n2315\n5132"],["15 14\n1 2\n2 3\n3 4\n4 5\n5 6\n6 7\n7 8\n8 9\n9 10\n10 11\n11 12\n12 13\n13 14\n14 15","678925929\n678925929\n678862929\n678787329\n678709839\n678632097\n178554320\n218476543\n321398766\n431520989\n542453212\n653475435\n764507558\n875540761\n986574081"]],"created_at":"2026-03-03 11:09:25"}}