{"problem":{"name":"Two Spanning Trees","description":{"content":"You are given an undirected graph $G$ with $N$ vertices and $M$ edges. $G$ is **simple** (it has no self-loops and multiple edges) and **connected**. For $i = 1, 2, \\ldots, M$, the $i$\\-th edge is an ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc251_f"},"statements":[{"statement_type":"Markdown","content":"You are given an undirected graph $G$ with $N$ vertices and $M$ edges. $G$ is **simple** (it has no self-loops and multiple edges) and **connected**.\nFor $i = 1, 2, \\ldots, M$, the $i$\\-th edge is an undirected edge $\\lbrace u_i, v_i \\rbrace$ connecting Vertices $u_i$ and $v_i$.\nConstruct two spanning trees $T_1$ and $T_2$ of $G$ that satisfy both of the two conditions below. ($T_1$ and $T_2$ do not necessarily have to be different spanning trees.)\n\n*   $T_1$ satisfies the following.\n    \n    > If we regard $T_1$ as a rooted tree rooted at Vertex $1$, for any edge $\\lbrace u, v \\rbrace$ of $G$ not contained in $T_1$, one of $u$ and $v$ is an ancestor of the other in $T_1$.\n    \n*   $T_2$ satisfies the following.\n    \n    > If we regard $T_2$ as a rooted tree rooted at Vertex $1$, there is no edge $\\lbrace u, v \\rbrace$ of $G$ not contained in $T_2$ such that one of $u$ and $v$ is an ancestor of the other in $T_2$.\n    \n\nWe can show that there always exists $T_1$ and $T_2$ that satisfy the conditions above.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $N-1 \\leq M \\leq \\min\\lbrace 2 \\times 10^5, N(N-1)/2 \\rbrace$\n*   $1 \\leq u_i, v_i \\leq N$\n*   All values in input are integers.\n*   The given graph is simple and connected.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_M$ $v_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc251_f","tags":[],"sample_group":[["6 8\n5 1\n4 3\n1 4\n3 5\n1 2\n2 6\n1 6\n4 2","1 4\n4 3\n5 3\n4 2\n6 2\n1 5\n5 3\n1 4\n2 1\n1 6\n\nIn the Sample Output above, $T_1$ is a spanning tree of $G$ containing $5$ edges $\\lbrace 1, 4 \\rbrace, \\lbrace 4, 3 \\rbrace, \\lbrace 5, 3 \\rbrace, \\lbrace 4, 2 \\rbrace, \\lbrace 6, 2 \\rbrace$. This $T_1$ satisfies the condition in the Problem Statement. Indeed, for each edge of $G$ not contained in $T_1$:\n\n*   for edge $\\lbrace 5, 1 \\rbrace$, Vertex $1$ is an ancestor of $5$;\n*   for edge $\\lbrace 1, 2 \\rbrace$, Vertex $1$ is an ancestor of $2$;\n*   for edge $\\lbrace 1, 6 \\rbrace$, Vertex $1$ is an ancestor of $6$.\n\n$T_2$ is another spanning tree of $G$ containing $5$ edges $\\lbrace 1, 5 \\rbrace, \\lbrace 5, 3 \\rbrace, \\lbrace 1, 4 \\rbrace, \\lbrace 2, 1 \\rbrace, \\lbrace 1, 6 \\rbrace$. This $T_2$ satisfies the condition in the Problem Statement. Indeed, for each edge of $G$ not contained in $T_2$:\n\n*   for edge $\\lbrace 4, 3 \\rbrace$, Vertex $4$ is not an ancestor of Vertex $3$, and vice versa;\n*   for edge $\\lbrace 2, 6 \\rbrace$, Vertex $2$ is not an ancestor of Vertex $6$, and vice versa;\n*   for edge $\\lbrace 4, 2 \\rbrace$, Vertex $4$ is not an ancestor of Vertex $2$, and vice versa."],["4 3\n3 1\n1 2\n1 4","1 2\n1 3\n1 4\n1 4\n1 3\n1 2\n\nTree $T$, containing $3$ edges $\\lbrace 1, 2\\rbrace, \\lbrace 1, 3 \\rbrace, \\lbrace 1, 4 \\rbrace$, is the only spanning tree of $G$. Since there are no edges of $G$ that are not contained in $T$, obviously this $T$ satisfies the conditions for both $T_1$ and $T_2$."]],"created_at":"2026-03-03 11:01:14"}}