35:I[290370,["/_next/static/immutable/chunks/16vlcskdgrilg.js","/_next/static/immutable/chunks/2fcecmiom-yvu.js","/_next/static/immutable/chunks/07tue-l4qhy1z.js","/_next/static/immutable/chunks/1gw-s2qr8_kwk.js","/_next/static/immutable/chunks/2ol9wyej_s9h-.js","/_next/static/immutable/chunks/20gnsl3b8ay94.js","/_next/static/immutable/chunks/0vj574x3q80w8.js","/_next/static/immutable/chunks/437mepgwkzb8b.js","/_next/static/immutable/chunks/1b4admyuy4r2b.js","/_next/static/immutable/chunks/3tw_xszkea-1d.js","/_next/static/immutable/chunks/3vuhqfn8nseb-.js","/_next/static/immutable/chunks/1sxrvy1s6kjvn.js","/_next/static/immutable/chunks/1atq4abfx_cwi.js","/_next/static/immutable/chunks/0tzrsu2md_yna.js","/_next/static/immutable/chunks/2ke2tvdiokend.js","/_next/static/immutable/chunks/103b5z0pgu--4.js","/_next/static/immutable/chunks/1luxevw57bu34.js","/_next/static/immutable/chunks/297ee9kns0rn0.js","/_next/static/immutable/chunks/2o2m33q5br6xr.js","/_next/static/immutable/chunks/1-37b7d009rvw.js"],"default"] 36:I[218728,["/_next/static/immutable/chunks/16vlcskdgrilg.js","/_next/static/immutable/chunks/2fcecmiom-yvu.js","/_next/static/immutable/chunks/07tue-l4qhy1z.js","/_next/static/immutable/chunks/1gw-s2qr8_kwk.js","/_next/static/immutable/chunks/2ol9wyej_s9h-.js","/_next/static/immutable/chunks/20gnsl3b8ay94.js","/_next/static/immutable/chunks/0vj574x3q80w8.js","/_next/static/immutable/chunks/437mepgwkzb8b.js","/_next/static/immutable/chunks/1b4admyuy4r2b.js","/_next/static/immutable/chunks/3tw_xszkea-1d.js","/_next/static/immutable/chunks/3vuhqfn8nseb-.js","/_next/static/immutable/chunks/1sxrvy1s6kjvn.js","/_next/static/immutable/chunks/1atq4abfx_cwi.js","/_next/static/immutable/chunks/0tzrsu2md_yna.js","/_next/static/immutable/chunks/2ke2tvdiokend.js","/_next/static/immutable/chunks/103b5z0pgu--4.js","/_next/static/immutable/chunks/1luxevw57bu34.js","/_next/static/immutable/chunks/297ee9kns0rn0.js","/_next/static/immutable/chunks/2o2m33q5br6xr.js","/_next/static/immutable/chunks/1-37b7d009rvw.js"],"default"] 37:T71b,#include "testlib.h" #include using namespace std; string normalize(string s) { for (char &c : s) c = (char)tolower(c); return s; } int main(int argc, char *argv[]) { registerTestlibCmd(argc, argv); int t = inf.readInt(); for (int tc = 1; tc <= t; tc++) { long long a = inf.readLong(); long long b = inf.readLong(); long long c = inf.readLong(); string ans = normalize(ouf.readToken("[A-Za-z]+", "answer")); bool possible = ((a + b + c) % 2 == 0); if (ans == "no") { if (possible) { quitf(_wa, "test case %d: participant printed No, but an answer exists", tc); } continue; } if (ans != "yes") { quitf(_pe, "test case %d: expected Yes or No, found '%s'", tc, ans.c_str()); } if (!possible) { quitf(_wa, "test case %d: participant printed Yes, but no answer exists", tc); } long long a1 = ouf.readLong(); long long b1 = ouf.readLong(); long long c1 = ouf.readLong(); long long a2 = ouf.readLong(); long long b2 = ouf.readLong(); long long c2 = ouf.readLong(); if (a1 < 0 || b1 < 0 || c1 < 0 || a2 < 0 || b2 < 0 || c2 < 0) { quitf(_wa, "test case %d: all printed values must be non-negative", tc); } if (a1 + a2 != a || b1 + b2 != b || c1 + c2 != c) { quitf(_wa, "test case %d: printed values do not split a, b, c correctly", tc); } if (a1 + b1 + c1 != a2 + b2 + c2) { quitf(_wa, "test case %d: the two sums are not equal", tc); } } if (!ouf.seekEof()) { quitf(_pe, "extra non-whitespace tokens after the required output"); } quitf(_ok, "accepted"); }38:Tc2a,#include #include "testlib.h" using namespace std; static string toLowerString(string s) { for (char &c : s) c = (char)tolower(c); return s; } static long long keyEdge(int u, int v) { if (u > v) swap(u, v); return 1LL * u * 1000000LL + v; } int main(int argc, char *argv[]) { registerTestlibCmd(argc, argv); int t = inf.readInt(); for (int tc = 1; tc <= t; tc++) { int n = inf.readInt(); int m = inf.readInt(); vector> adj(n + 1); unordered_set edges; edges.reserve((size_t)m * 2 + 10); for (int i = 0; i < m; i++) { int u = inf.readInt(); int v = inf.readInt(); adj[u].push_back(v); adj[v].push_back(u); edges.insert(keyEdge(u, v)); } vector mark(n + 1, 0); int timer = 0; set rem; for (int i = 1; i <= n; i++) rem.insert(i); queue q; rem.erase(1); q.push(1); int seen = 0; while (!q.empty()) { int u = q.front(); q.pop(); seen++; ++timer; for (int v : adj[u]) { mark[v] = timer; } for (auto it = rem.begin(); it != rem.end(); ) { int v = *it; // If uv is not an edge of the input graph, then uv is an edge of G. if (mark[v] != timer) { it = rem.erase(it); q.push(v); } else { ++it; } } } bool exists = (seen == n); string verdict = toLowerString(ouf.readToken()); if (verdict != "yes" && verdict != "no") { quitf(_wa, "Test case %d: expected Yes or No, found '%s'.", tc, verdict.c_str()); } if (!exists) { if (verdict == "yes") { quitf(_wa, "Test case %d: participant printed Yes, but no Hamiltonian path exists.", tc); } continue; } if (verdict == "no") { quitf(_wa, "Test case %d: participant printed No, but a Hamiltonian path exists.", tc); } vector path(n); vector used(n + 1, 0); for (int i = 0; i < n; i++) { path[i] = ouf.readInt(1, n); if (used[path[i]]) { quitf(_wa, "Test case %d: vertex %d appears more than once in the path.", tc, path[i]); } used[path[i]] = 1; } for (int i = 0; i + 1 < n; i++) { int u = path[i]; int v = path[i + 1]; if (edges.count(keyEdge(u, v))) { quitf(_wa, "Test case %d: vertices %d and %d are consecutive, but this edge exists in the input graph, so it does not exist in G.", tc, u, v); } } } if (!ouf.seekEof()) { quitf(_wa, "Extra non-whitespace tokens after the required output."); } quitf(_ok, "Output is valid."); }19:["$","div",null,{"children":[["$","$L35",null,{"contestId":"6a4003c6a236ad89e91af2c9","contestType":"cp","contestNumber":15,"contestUrlId":"15","initialIsRegistered":false}],["$","$L36",null,{"contest":{"contestNumber":15,"title":"Repovive Starter Round 4","startDate":"2026-07-05T14:35:00.000Z","endDate":"2026-07-05T16:35:00.000Z","urlSlug":"$undefined","problemDisplay":"letters","requiresPremium":false,"lobbyProblemsCount":7,"isProblemSet":false,"contestType":"cp","adminOnly":false,"isWeeklyChallenge":false,"weekNumber":"$undefined","ratedMaxTier":"$undefined","announcements":[{"id":"508c0316-9b70-4b4b-a6fe-17705c066faa","message":"There was an issue on G about the white spaces. It is fixed now, and all submissions have been rejudged.","createdAt":"2026-07-05T15:35:38.600Z"},{"id":"d7f9a821-44cd-491b-82e4-0b24cd691c2a","message":"Problem F\nThe samples were fixed.","createdAt":"2026-07-05T15:29:40.080Z"}]},"problems":[{"_id":"6a48604716b6faa04ec864b5","contestId":"6a4003c6a236ad89e91af2c9","slug":"different-parity","title":"Different Parity","description":"You are given two integers $l$ and $r$.\n\nConsider all integers from $l$ to $r$, inclusive. Determine whether this interval contains at least one odd integer and at least one even integer.","constraints":"- $1 \\le l \\le r \\le 10^5$","difficulty":"easy","order":1,"label":"$undefined","releaseDay":"$undefined","points":500,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"5 5\n","expectedOutput":"No\n","isSample":true,"hidden":false,"explanation":"The interval contains only the number $5$, which is odd. There is no even number in the interval.\n"},{"input":"10 11\n","expectedOutput":"Yes\n","isSample":true,"hidden":false,"explanation":"The interval contains $10$ and $11$. One of them is even and the other one is odd.\n"},{"input":"1 100000\n","expectedOutput":"Yes\n","isSample":true,"hidden":false,"explanation":"The interval contains many integers, including both odd and even integers.\n"}],"sampleCount":3,"inputFormat":"$$$\nl \\quad r\n$$","outputFormat":"Print `Yes` if the interval contains both an odd integer and an even integer.\n\nOtherwise, print `No`.","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":95,"attemptedCount":97,"tags":["math","implementation"],"learnPages":[{"title":"The only important thing is the length","content":"If $l=r$, the interval contains exactly one integer. One integer cannot be both odd and even, so the answer is `No`.\n\nIf $l c_j$.\n\nYour task is to find how many distinct values of $\\operatorname{inv}(a) + \\operatorname{inv}(b)$ can be obtained after performing the operations.","constraints":"- $1 \\le n \\le 2 \\times 10^5$\n- $a_1, a_2, \\ldots, a_n$ is a permutation of $1, 2, \\ldots, n$\n- $b_1, b_2, \\ldots, b_n$ is a permutation of $1, 2, \\ldots, n$","difficulty":"medium","order":5,"label":"$undefined","releaseDay":"$undefined","points":2500,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"3\n1 2 3\n1 2 3\n","expectedOutput":"4\n","isSample":true,"hidden":false,"explanation":"With no operation, the arrays stay $[1, 2, 3]$ and $[1, 2, 3]$, so the total is $0$.\n\nSwapping indices $1$ and $2$ makes the arrays $[2, 1, 3]$ and $[2, 1, 3]$, so the total is $2$.\n\nSwapping indices $1$ and $2$, then indices $2$ and $3$, makes the arrays $[2, 3, 1]$ and $[2, 3, 1]$, so the total is $4$.\n\nSwapping indices $1$ and $3$ makes the arrays $[3, 2, 1]$ and $[3, 2, 1]$, so the total is $6$.\n\nThus there are $4$ possible values.\n"},{"input":"3\n1 2 3\n3 2 1\n","expectedOutput":"1\n","isSample":true,"hidden":false,"explanation":"With no operation, the arrays are $[1, 2, 3]$ and $[3, 2, 1]$, and the total is $3$.\n\nSwapping indices $1$ and $2$ makes the arrays $[2, 1, 3]$ and $[2, 3, 1]$, and the total is still $3$.\n\nChecking the other final arrangements gives the same total, so only $1$ value is possible.\n"},{"input":"4\n1 2 3 4\n1 3 2 4\n","expectedOutput":"6\n","isSample":true,"hidden":false,"explanation":"With no operation, the arrays stay $[1, 2, 3, 4]$ and $[1, 3, 2, 4]$, so the total is $1$.\n\nFor example, after swapping indices $1$ and $2$, then indices $2$ and $4$, the arrays become $[2, 4, 3, 1]$ and $[3, 4, 2, 1]$, so the total is $9$.\n"}],"sampleCount":3,"inputFormat":"$$$\n\\begin{array}{l}\nn \\\\\na_1 \\quad a_2 \\quad \\cdots \\quad a_n \\\\\nb_1 \\quad b_2 \\quad \\cdots \\quad b_n\n\\end{array}\n$$","outputFormat":"Output a single integer, the number of distinct possible values of $\\operatorname{inv}(a) + \\operatorname{inv}(b)$.","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":27,"attemptedCount":32,"tags":["data structures","combinatorics","sortings"],"learnPages":[{"title":"Any Order Is Possible","content":"Each operation swaps the same two positions in both arrays. Therefore, the pair of values currently at these positions moves together.\n\nSince arbitrary swaps are allowed, we can make the pairs appear in any order we want."},{"title":"Looking at One Pair of Positions","content":"Consider two original positions $x$ and $y$.\n\nBecause both arrays are permutations, $a_x \\ne a_y$ and $b_x \\ne b_y$.\n\nIf $a_x < a_y$ and $b_x > b_y$, then whichever one is placed first, exactly one of the two arrays gets an inversion from this pair. The same is true for the symmetric case. Such a pair always contributes $1$.\n\nOtherwise, the two values have the same relative order in both arrays. Then placing them in that order contributes $0$, and placing them in the opposite order contributes $2$."},{"title":"Which Values Can Appear?","content":"Sort the positions by increasing value of $a$. Look at the sequence of their $b$ values.\n\nLet $D$ be the number of inversions in this sequence. These are exactly the pairs whose relative orders in $a$ and $b$ are opposite, so they always contribute $1$.\n\nLet $C$ be the number of remaining pairs. If exactly $k$ of these $C$ pairs are placed in the opposite order, the sum becomes $D + 2k$.\n\nIt remains to see that every $k$ from $0$ to $C$ is possible. Start from the order sorted by $a$, then reverse this order using adjacent swaps. During this process, every pair is swapped exactly once. Whenever a pair from the $C$ remaining pairs is swapped, $k$ increases by $1$; otherwise $k$ does not change. Hence all values $k=0,1,\\ldots,C$ appear."},{"title":"Computing the Answer","content":"The total number of pairs is $n(n-1)/2$.\n\nAfter sorting positions by $a$, compute the number $D$ of inversions in the obtained sequence of $b$ values using a Fenwick tree.\n\nThen $C = n(n-1)/2 - D$, and the number of possible sums is $C+1$.\n\nThe time complexity is $O(n \\log n)$."}],"hasLearnContent":true,"likeCount":14,"neutralCount":0,"dislikeCount":4,"isInteractive":false,"interactor":"$undefined","hidden":false,"sampleTestCases":"$undefined","samplesDiverged":"$undefined","sourceAttribution":"$undefined","source":"$undefined","validatorSource":"$undefined","correctSolution":"$undefined","generators":"$undefined","genDataContent":"$undefined","readiness":"$undefined","linkedBuildSessionId":"$undefined","isLinked":"$undefined","authors":[{"_id":"6910dbd9f636aa34a20ab8b2","name":"Bahamin Shafaghi"}],"statementOverrides":"$undefined","createdAt":"2026-07-03T13:37:58.301Z","updatedAt":"2026-07-06T02:51:27.033Z"},{"_id":"6a47c2ff02b1cd6a777f3e72","contestId":"6a4003c6a236ad89e91af2c9","slug":"magnetic-path","title":"Magnetic Path","description":"You are given a tree with $n$ vertices, numbered from $1$ to $n$.\n\nThere are two pieces of iron. Initially, one of them is on vertex $1$, and the other one is on vertex $n$.\n\nIn one operation, you choose a vertex $v$ and place a magnet on it for one second. During this second, each piece of iron behaves independently:\n\n- if the piece is already on vertex $v$, it does not move;\n- otherwise, it moves by one edge along the unique simple path from its current vertex to $v$.\n\nAfter that, the magnet is removed.\n\nA sequence of operations is successful if after all operations both pieces of iron are on the same vertex.\n\nAmong all successful sequences with the minimum possible number of operations, count how many different sequences exist. Two sequences are considered different if for some operation position, the chosen magnet vertices are different.\n\nOutput the answer modulo $998244353$.\n\nIf the two pieces of iron are already on the same vertex, the empty sequence is considered the only optimal sequence.","constraints":"- $1 \\le t \\le 10^4$\n- $1 \\le n \\le 2 \\times 10^5$\n- The sum of $n$ over all test cases is at most $2 \\times 10^5$\n- The given graph is a tree\n- The distance between vertices $1$ and $n$ is even","difficulty":"medium","order":6,"label":"$undefined","releaseDay":"$undefined","points":3000,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"5\n1\n3\n1 2\n2 3\n4\n2 1\n2 4\n2 3\n7\n1 2\n2 3\n3 4\n4 7\n3 5\n3 6\n9\n1 2\n2 3\n3 4\n4 5\n5 6\n6 9\n3 7\n5 8\n","expectedOutput":"1\n1\n2\n15\n35\n","isSample":true,"hidden":false,"explanation":"The two pieces are already on the same vertex, so no operation is needed. The empty sequence is the only optimal sequence.\n`\nOne operation is necessary. Choosing vertex 2 moves both pieces to vertex 2, so there is exactly one optimal sequence.\n`\nOne operation is necessary. Choosing vertex 2 or vertex 3 moves both pieces to vertex 2, so there are two optimal sequences.\n`\nTwo operations are necessary. The first magnet can be placed on one of vertices 2, 3, 4, 5, 6. After that, the second magnet can be placed on one of vertices 3, 5, 6. Hence there are 15 optimal sequences.\n`\nThree operations are necessary. The numbers of possible choices in the three operations are 7, 5, and 1, respectively, so the answer is 35.\n","displayInput":"5\n`\n1\n`\n3\n1 2\n2 3\n`\n4\n2 1\n2 4\n2 3\n`\n7\n1 2\n2 3\n3 4\n4 7\n3 5\n3 6\n`\n9\n1 2\n2 3\n3 4\n4 5\n5 6\n6 9\n3 7\n5 8","displayOutput":"1\n`\n1\n`\n2\n`\n15\n`\n35"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\\\\nu_1 \\quad v_1 \\\\\nu_2 \\quad v_2 \\\\\n\\vdots \\\\\nu_{n-1} \\quad v_{n-1}\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\nans\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":29,"attemptedCount":31,"tags":["trees","dfs and similar","combinatorics"],"learnPages":[{"title":"Minimum number of operations","content":"Let the current vertices of the two iron pieces be $x$ and $y$. In one operation, each piece moves by at most one edge, so the distance between them can decrease by at most $2$.\n\nLet $D$ be the distance between vertices $1$ and $n$. Since $D$ is guaranteed to be even, at least $D/2$ operations are needed.\n\nThis lower bound is attainable: if we always choose a magnet vertex whose projection on the current path between the two pieces is an internal vertex of that path, both pieces move one step toward each other. Therefore the distance decreases by exactly $2$ each time, and after $D/2$ operations they meet."},{"title":"Projection on the main path","content":"Write the path from vertex $1$ to vertex $n$ as $p_0, p_1, \\ldots, p_D$, where $p_0 = 1$ and $p_D = n$.\n\nAfter $t$ optimal operations, the two pieces must be on $p_t$ and $p_{D-t}$. This is because every optimal operation must decrease their distance by exactly $2$.\n\nNow consider choosing a magnet vertex $v$. Look at the closest vertex to $v$ on the original path $p_0, p_1, \\ldots, p_D$; call it the projection of $v$.\n\nAt step $t$, the operation is optimal exactly when this projection is one of $p_{t+1}, p_{t+2}, \\ldots, p_{D-t-1}$. Then both pieces move toward the inside of the current path. If the projection is one of the two endpoints, only one piece moves toward the other, so the distance decreases by only $1$, which cannot happen in an optimal sequence."},{"title":"Counting choices at each step","content":"For every vertex $p_i$ on the path from $1$ to $n$, define $w_i$ as the number of tree vertices whose projection on this path is $p_i$.\n\nEquivalently, remove all edges of the path. Then $w_i$ is the size of the component containing $p_i$.\n\nAt step $t$, the valid projections are $p_{t+1}, p_{t+2}, \\ldots, p_{D-t-1}$. Therefore the number of possible magnet vertices at this step is $w_{t+1} + w_{t+2} + \\cdots + w_{D-t-1}$.\n\nThe choices of different steps are independent after we know that every step is optimal, because all valid choices at step $t$ move the two pieces to the same next pair of vertices, namely $p_{t+1}$ and $p_{D-t-1}$.\n\nThus the answer is the product of these values for all $0 \\le t < D/2$, modulo $998244353$."},{"title":"Implementation","content":"First find the path from vertex $1$ to vertex $n$ using DFS or BFS and parent pointers. Mark all vertices on this path.\n\nFor each path vertex $p_i$, run DFS into all adjacent branches that are not on the path. The total number of visited vertices over all these DFS calls is $O(n)$, so all values $w_i$ are computed in linear time.\n\nBuild prefix sums over $w_i$. Then each value $w_{t+1} + \\cdots + w_{D-t-1}$ is obtained in $O(1)$.\n\nThe total time complexity is $O(n)$ per test case, and the memory usage is $O(n)$."}],"hasLearnContent":true,"likeCount":13,"neutralCount":0,"dislikeCount":2,"isInteractive":false,"interactor":"$undefined","hidden":false,"sampleTestCases":"$undefined","samplesDiverged":"$undefined","sourceAttribution":"$undefined","source":"$undefined","validatorSource":"$undefined","correctSolution":"$undefined","generators":"$undefined","genDataContent":"$undefined","readiness":"$undefined","linkedBuildSessionId":"$undefined","isLinked":"$undefined","authors":[{"_id":"6910edb50cda69581e13124c","name":"Hamid Shafi"}],"statementOverrides":"$undefined","createdAt":"2026-07-03T14:11:11.799Z","updatedAt":"2026-07-06T02:51:27.033Z"},{"_id":"6a46e9a83d4e47db1020f34b","contestId":"6a4003c6a236ad89e91af2c9","slug":"complementary-path","title":"Complementary Path","description":"You are given the complement of a simple undirected graph $G$.\n\nMore precisely, the input graph is a graph $\\overline{G}$ on vertices $1,2,\\ldots,n$. \nFor every two distinct vertices $u$ and $v$, the edge $(u,v)$ exists in $G$ if and only if it does not exist in $\\overline{G}$.\n\nThe input graph $\\overline{G}$ has no triangle. In other words, there are no three distinct vertices $a$, $b$, and $c$ such that all three edges $(a,b)$, $(b,c)$, and $(c,a)$ exist in the input graph.\n\nFor each test case, find a Hamiltonian path in $G$, or determine that no such path exists.\n\nA Hamiltonian path is an ordering of all $n$ vertices $p_1,p_2,\\ldots,p_n$ such that for every $1 \\le i < n$, the edge $(p_i,p_{i+1})$ exists in $G$.","constraints":"- $1 \\le t \\le 10^4$\n- $1 \\le n \\le 2 \\times 10^5$\n- $0 \\le m \\le 2 \\times 10^5$\n- The input graph is simple and undirected.\n- The input graph has no triangle.\n- The sum of $n$ over all test cases is at most $2 \\times 10^5$.\n- The sum of $m$ over all test cases is at most $2 \\times 10^5$.","difficulty":"medium","order":7,"label":"$undefined","releaseDay":"$undefined","points":3500,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"5\n1 0\n3 2\n1 2\n2 3\n4 0\n4 4\n1 3\n1 4\n2 3\n2 4\n5 5\n1 2\n2 3\n3 4\n4 5\n5 1\n","expectedOutput":"Yes\n1\nNo\nYes\n4 3 2 1\nNo\nYes\n2 5 3 1 4\n","isSample":true,"hidden":false,"explanation":"The only vertex is already a Hamiltonian path.\n`\nIn the complement graph, vertex $2$ is isolated, so no Hamiltonian path can use all vertices.\n`\nThe given graph has no edges, so its complement is complete. The printed ordering is therefore valid.\n`\nThe complement graph has only the edges $1$-$2$ and $3$-$4$, so it is disconnected and cannot have a Hamiltonian path.\n`\nFor the printed ordering, every consecutive pair is a non-edge of the given graph, so every consecutive pair is an edge of its complement.\n","displayInput":"5\n`\n1 0\n`\n3 2\n1 2\n2 3\n`\n4 0\n`\n4 4\n1 3\n1 4\n2 3\n2 4\n`\n5 5\n1 2\n2 3\n3 4\n4 5\n5 1","displayOutput":"Yes\n1\n`\nNo\n`\nYes\n4 3 2 1\n`\nNo\n`\nYes\n2 5 3 1 4"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\quad m \\\\\nu_1 \\quad v_1 \\\\\nu_2 \\quad v_2 \\\\\n\\vdots \\\\\nu_m \\quad v_m\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"For each test case, if there is no Hamiltonian path in $G$, output\n\n$$\n\\text{No}\n$$\n\nOtherwise, output\n\n$$\n\\begin{array}{l}\n\\text{Yes} \\\\\np_1 \\quad p_2 \\quad \\cdots \\quad p_n\n\\end{array}\n$$\n\nwhere $p_1,p_2,\\ldots,p_n$ is a Hamiltonian path in $G$.\n\nYou may print each letter in any case.","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"custom","sourceCode":"$38"},"solvedCount":7,"attemptedCount":10,"tags":["graphs","dfs and similar","data structures","constructive"],"learnPages":[{"title":"Looking at the complement","content":"Call the given graph $H$, and call its complement $G$.\n\nSince $H$ has no triangle, there are no three vertices in $G$ that are pairwise non-adjacent. Indeed, three pairwise non-adjacent vertices in $G$ would form a triangle in $H$.\n\nSo, among any three vertices of $G$, at least one pair is connected by an edge.\n\nFirst, if $G$ is not connected, a Hamiltonian path cannot exist. Therefore we only need to show how to construct a path when $G$ is connected."},{"title":"Adding one vertex to the path","content":"Assume we already have a path $v_1,v_2,\\ldots,v_k$ in $G$, and we want to add a new vertex $x$. Also assume $x$ has at least one edge to the current path.\n\nIf $xv_1$ is an edge, put $x$ at the beginning. If $xv_k$ is an edge, put $x$ at the end.\n\nNow suppose $x$ is not adjacent to either end. Then $v_1v_k$ must be an edge; otherwise $x,v_1,v_k$ would be three pairwise non-adjacent vertices in $G$, which is impossible.\n\nTake any vertex $v_i$ on the path adjacent to $x$. It is not an end. Then\n\n$$\nx, v_i, v_{i+1}, \\ldots, v_k, v_1, v_2, \\ldots, v_{i-1}\n$$\n\nis a valid path. The only new edges used are $xv_i$ and $v_kv_1$, and both exist."},{"title":"Finding an order of insertion","content":"We need an order where every new vertex has an edge to some previous vertex in $G$.\n\nThis is exactly what a BFS or DFS order gives in a connected graph. We run BFS on $G$, but $G$ is not given explicitly. The input gives $H$, the complement of $G$.\n\nTo process a vertex $u$, mark all neighbors of $u$ in $H$. Every still-unvisited vertex that is not marked is adjacent to $u$ in $G$, so it can be visited next.\n\nA set of unvisited vertices lets us remove all such vertices efficiently while scanning it."},{"title":"Implementation details","content":"During the second phase, keep the current path as a linked list with arrays `next` and `prev`.\n\nFor a new vertex $x$, mark all neighbors of $x$ in $H$. A vertex not marked is adjacent to $x$ in $G$.\n\nIf the head or the tail is adjacent to $x$, insert $x$ there. Otherwise scan from the head until the first vertex $v_i$ adjacent to $x$ is found, and perform the rotation described before.\n\nThe scan passes only through vertices adjacent to $x$ in $H$ before it stops, so over all insertions these scans cost $O(n+m)$.\n\nThe BFS on the complement costs $O((n+m)\\log n)$ with a set. The total complexity is $O((n+m)\\log n)$ per input size sum, and the memory usage is $O(n+m)$."}],"hasLearnContent":true,"likeCount":4,"neutralCount":0,"dislikeCount":0,"isInteractive":false,"interactor":"$undefined","hidden":false,"sampleTestCases":"$undefined","samplesDiverged":"$undefined","sourceAttribution":"$undefined","source":"$undefined","validatorSource":"$undefined","correctSolution":"$undefined","generators":"$undefined","genDataContent":"$undefined","readiness":"$undefined","linkedBuildSessionId":"$undefined","isLinked":"$undefined","authors":[{"_id":"6910edb50cda69581e13124c","name":"Hamid Shafi"}],"statementOverrides":"$undefined","createdAt":"2026-07-02T22:43:52.129Z","updatedAt":"2026-07-06T02:51:27.033Z"}],"contestId":"6a4003c6a236ad89e91af2c9","contestUrlId":"15","isAdmin":false,"isTester":false,"isStarted":true,"isRegistered":false,"canRegister":false,"problemStatusMap":{},"isPremiumBlocked":false,"sponsorshipSnapshot":"$18:props:children:1:props:children:0:props:sponsorshipSnapshot","recentRoundParticipantCounts":[93,108,96],"participationMode":null,"virtualStartTime":null,"contestDurationMs":7200000}]]}]

ADifferent Parity	500	95/97
BBalanced Trio	1000	82/90
CCorner Meeting	1500	78/81
DDistant Transfers	2000	56/62
ESynchronized Inversions	2500	27/32
FMagnetic Path	3000	29/31
GComplementary Path	3500	7/10