{"problem":{"name":"K2. MST(a.k.a. Most Stupid Technique)","description":{"content":"During a programming contest, Mr. Search Tree (a.k.a. MST) forgot how to implement Kruskal's and Prim's algorithms. In a moment of desperation, he wrote a DFS that always follows the smallest availabl","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CFK2"},"statements":[{"statement_type":"Markdown","content":"During a programming contest, Mr. Search Tree (a.k.a. MST) forgot how to implement Kruskal's and Prim's algorithms. In a moment of desperation, he wrote a DFS that always follows the smallest available edge first. Strangely enough, it passed.\n\nNow he wonders: for which starting nodes does his \"Most Stupid Technique\" accidentally produce a correct minimum spanning tree$\"\"^dagger$ ?\n\nFormally, given a connected undirected graph with $n$ nodes and $m$ edges, the $i$-th edge has weight $i$, and here is the algorithm he used:\n\nIn other words, _findMST(u)_ performs a DFS starting from vertex $u$, always choosing the smallest-weight unvisited edge from the current node and includes it in the tree.\n\nAlthough this always produces a spanning tree, it doesn't always yield a minimum one.\n\nYour task is to determine, for each node $i$ from $1$ to $n$, whether _findMST(i)_ returns a minimum spanning tree.\n\n$\"\"^dagger$ A minimum spanning tree (MST) of a connected undirected graph is a subset of the edges that forms a tree connecting all the vertices and has the minimum possible total edge weight among all such trees.\n\nThe first line contains two integers $n$ and $m$ ($2 <= n <= 10^5, n -1 <= m <= 2 dot.op 10^5$), denoting the number of vertices and edges. \n\nFor the following $m$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 <= u_i, v_i <= n, u_i eq.not v_i$), denoting an undirected edge between $u_i$ and $v_i$.\n\nThe $i$-th edge ($1$-based index in input) has weight $i$.\n\nIt's guaranteed that the graph is connected and contains no duplicate edges.\n\nOutput one line containing a binary string of length $n$.\n\nThe i-th character should be '$1$'(without quotes) if the tree produced by running the algorithm above starting from node i is a minimum spanning tree, and '$0$'(without quotes) otherwise.\n\nThe sample case is shown below:\n\nThe graph for the sample \n\nThe only minimum spanning tree (MST) of this graph includes the edges with weights $1$, $2$, $4$, and $5$, which has a total edge weight of 12.\n\nWe simulate the algorithm _findMST(u)_ for each $u$ from $1$ to $5$:\n\nThus, the output is _01111_.\n\n## Input\n\nThe first line contains two integers $n$ and $m$ ($2 <= n <= 10^5, n -1 <= m <= 2 dot.op 10^5$), denoting the number of vertices and edges. For the following $m$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 <= u_i, v_i <= n, u_i eq.not v_i$), denoting an undirected edge between $u_i$ and $v_i$.The $i$-th edge ($1$-based index in input) has weight $i$.It's guaranteed that the graph is connected and contains no duplicate edges.\n\n## Output\n\nOutput one line containing a binary string of length $n$.The i-th character should be '$1$'(without quotes) if the tree produced by running the algorithm above starting from node i is a minimum spanning tree, and '$0$'(without quotes) otherwise.\n\n[samples]\n\n## Note\n\nThe sample case is shown below: The graph for the sample The only minimum spanning tree (MST) of this graph includes the edges with weights $1$, $2$, $4$, and $5$, which has a total edge weight of 12.We simulate the algorithm _findMST(u)_ for each $u$ from $1$ to $5$:  _findMST(1)_ starts from node $1$ and visits edge $1$ first (to node $2$). Then at node $2$, the smallest unvisited adjacent edge is edge $3$ (to node $3$), so it is selected instead of edge $2$. As a result, edge $3$ (which has higher weight than edge $2$) is included in the result, and the resulting tree includes the edges with weights $1$, $3$, $4$, and $5$, which has a total edge weight of 13; so it doesn't construct the MST of the graph.  _findMST(2)_, _findMST(3)_, _findMST(4)_, and _findMST(5)_ all happen to construct the correct MST. Thus, the output is _01111_.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"在一次编程竞赛中，Mr. Search Tree（又称 MST）忘记了如何实现 Kruskal 算法和 Prim 算法。在绝望之际，他写了一个 DFS，总是优先选择当前节点可用的最小边。奇怪的是，它通过了。\n\n现在他想知道：对于哪些起始节点，他的“最愚蠢技巧”会偶然产生正确的最小生成树$\"\"^dagger$？\n\n形式化地，给定一个包含 $n$ 个节点和 $m$ 条边的连通无向图，第 $i$ 条边的权重为 $i$，他使用的算法如下：\n\n换句话说，_findMST(u)_ 从顶点 $u$ 开始执行 DFS，始终从当前节点选择权重最小的未访问边，并将其加入树中。\n\n尽管该算法总是生成一棵生成树，但并不总是生成最小生成树。\n\n你的任务是确定对于每个节点 $i$（从 $1$ 到 $n$），_findMST(i)_ 是否返回一个最小生成树。\n\n$\"\"^dagger$ 一个连通无向图的最小生成树（MST）是指一组边的子集，它构成一棵连接所有顶点的树，且在所有此类树中具有最小的总边权。\n\n第一行包含两个整数 $n$ 和 $m$（$2 lt.eq n lt.eq 10^5, n -1 lt.eq m lt.eq 2 dot.op 10^5$），分别表示顶点数和边数。\n\n接下来的 $m$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 lt.eq u_i, v_i lt.eq n, u_i eq.not v_i$），表示 $u_i$ 和 $v_i$ 之间的无向边。\n\n第 $i$ 条边（输入中基于 1 的索引）的权重为 $i$。\n\n保证图是连通的，且不包含重复边。\n\n输出一行，包含一个长度为 $n$ 的二进制字符串。\n\n第 $i$ 个字符应为 '$1$'（不带引号），如果从节点 $i$ 开始运行上述算法所生成的树是最小生成树；否则为 '$0$'（不带引号）。\n\n样例情况如下所示：\n\n样例图\n\n该图唯一的最小生成树（MST）包含权重为 $1$、$2$、$4$ 和 $5$ 的边，总边权为 12。\n\n我们对每个 $u$ 从 $1$ 到 $5$ 模拟 _findMST(u)_：\n\n因此，输出为 _01111_。\n\n## Input\n\n第一行包含两个整数 $n$ 和 $m$（$2 lt.eq n lt.eq 10^5, n -1 lt.eq m lt.eq 2 dot.op 10^5$），表示顶点数和边数。接下来的 $m$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 lt.eq u_i, v_i lt.eq n, u_i eq.not v_i$），表示 $u_i$ 和 $v_i$ 之间的无向边。第 $i$ 条边（输入中基于 1 的索引）的权重为 $i$。保证图是连通的，且不包含重复边。\n\n## Output\n\n输出一行，包含一个长度为 $n$ 的二进制字符串。第 $i$ 个字符应为 '$1$'（不带引号），如果从节点 $i$ 开始运行上述算法所生成的树是最小生成树；否则为 '$0$'（不带引号）。\n\n[samples]\n\n## Note\n\n样例情况如下所示：样例图\n该图唯一的最小生成树（MST）包含权重为 $1$、$2$、$4$ 和 $5$ 的边，总边权为 12。\n我们对每个 $u$ 从 $1$ 到 $5$ 模拟 _findMST(u)_：\n_findMST(1)_ 从节点 $1$ 开始，首先访问边 $1$（到节点 $2$）。然后在节点 $2$，最小的未访问邻接边是边 $3$（到节点 $3$），因此选择它而非边 $2$。结果，边 $3$（其权重高于边 $2$）被包含在结果中，最终生成的树包含权重为 $1$、$3$、$4$ 和 $5$ 的边，总边权为 13；因此它没有构造出图的 MST。\n_findMST(2)_、_findMST(3)_、_findMST(4)_ 和 _findMST(5)_ 都恰好构造出了正确的 MST。因此，输出为 _01111_。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be a connected undirected graph with $ |V| = n $, $ |E| = m $.  \nFor $ i \\in \\{1, \\dots, m\\} $, edge $ e_i = (u_i, v_i) \\in E $ has weight $ w(e_i) = i $.  \n\nLet $ \\text{findMST}(u) $ denote the DFS traversal starting at node $ u $, at each step selecting the smallest-weight unvisited edge incident to the current node, and including it in the constructed tree.  \n\nLet $ T_u $ be the spanning tree produced by $ \\text{findMST}(u) $.  \nLet $ T^* $ be a minimum spanning tree of $ G $ (unique due to distinct edge weights).  \n\n**Constraints**  \n1. $ 2 \\le n \\le 10^5 $  \n2. $ n - 1 \\le m \\le 2 \\cdot 10^5 $  \n3. All edge weights are distinct and equal to their 1-based input index.  \n4. The graph is connected and has no duplicate edges.  \n\n**Objective**  \nFor each node $ i \\in \\{1, \\dots, n\\} $, determine whether $ T_i = T^* $.  \nOutput a binary string $ s $ of length $ n $, where:  \n$$\ns[i] = \n\\begin{cases}\n1 & \\text{if } T_i = T^* \\\\\n0 & \\text{otherwise}\n\\end{cases}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CFK2","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}