36:I[290370,["/_next/static/immutable/chunks/450p8-pxcf0ia.js","/_next/static/immutable/chunks/3asdwddb65r_7.js","/_next/static/immutable/chunks/11qxjuvxxj8-v.js","/_next/static/immutable/chunks/2ol9wyej_s9h-.js","/_next/static/immutable/chunks/3dqr5h54-q26k.js","/_next/static/immutable/chunks/0z1r4fy-dx8_h.js","/_next/static/immutable/chunks/1om2mt2f0a9n2.js","/_next/static/immutable/chunks/03jf6lfc9r-so.js","/_next/static/immutable/chunks/3mu0dqasw2v3x.js","/_next/static/immutable/chunks/437mepgwkzb8b.js","/_next/static/immutable/chunks/3v3xdl4a7xa4b.js","/_next/static/immutable/chunks/3_j9w0w1bg26d.js","/_next/static/immutable/chunks/3vuhqfn8nseb-.js","/_next/static/immutable/chunks/2ke2tvdiokend.js","/_next/static/immutable/chunks/1atq4abfx_cwi.js","/_next/static/immutable/chunks/37rc79uvtq2yl.js","/_next/static/immutable/chunks/034_v8m3bo14d.js","/_next/static/immutable/chunks/242a8c2jg1igi.js","/_next/static/immutable/chunks/0c5_sv5_129vb.js","/_next/static/immutable/chunks/1vvt2ge-jghht.js","/_next/static/immutable/chunks/18bin06et1f2f.js","/_next/static/immutable/chunks/3-n7byq0dh7z8.js","/_next/static/immutable/chunks/091zjp-oxk1vw.js"],"default"] 37:I[218728,["/_next/static/immutable/chunks/450p8-pxcf0ia.js","/_next/static/immutable/chunks/3asdwddb65r_7.js","/_next/static/immutable/chunks/11qxjuvxxj8-v.js","/_next/static/immutable/chunks/2ol9wyej_s9h-.js","/_next/static/immutable/chunks/3dqr5h54-q26k.js","/_next/static/immutable/chunks/0z1r4fy-dx8_h.js","/_next/static/immutable/chunks/1om2mt2f0a9n2.js","/_next/static/immutable/chunks/03jf6lfc9r-so.js","/_next/static/immutable/chunks/3mu0dqasw2v3x.js","/_next/static/immutable/chunks/437mepgwkzb8b.js","/_next/static/immutable/chunks/3v3xdl4a7xa4b.js","/_next/static/immutable/chunks/3_j9w0w1bg26d.js","/_next/static/immutable/chunks/3vuhqfn8nseb-.js","/_next/static/immutable/chunks/2ke2tvdiokend.js","/_next/static/immutable/chunks/1atq4abfx_cwi.js","/_next/static/immutable/chunks/37rc79uvtq2yl.js","/_next/static/immutable/chunks/034_v8m3bo14d.js","/_next/static/immutable/chunks/242a8c2jg1igi.js","/_next/static/immutable/chunks/0c5_sv5_129vb.js","/_next/static/immutable/chunks/1vvt2ge-jghht.js","/_next/static/immutable/chunks/18bin06et1f2f.js","/_next/static/immutable/chunks/3-n7byq0dh7z8.js","/_next/static/immutable/chunks/091zjp-oxk1vw.js"],"default"] 38:T7a3,#include "testlib.h" #include using namespace std; struct Rect { int r1, c1, r2, c2; }; long long scoreRect(const vector> &a, Rect r) { int mn = INT_MAX; for (int i = r.r1; i <= r.r2; i++) { for (int j = r.c1; j <= r.c2; j++) { mn = min(mn, a[i][j]); } } long long area = 1LL * (r.r2 - r.r1 + 1) * (r.c2 - r.c1 + 1); return 1LL * mn * area; } Rect readRect(InStream &s, int n, int m, const string &who) { int r1 = s.readInt(1, n, (who + ".r1").c_str()); int c1 = s.readInt(1, m, (who + ".c1").c_str()); int r2 = s.readInt(1, n, (who + ".r2").c_str()); int c2 = s.readInt(1, m, (who + ".c2").c_str()); if (r1 > r2 || c1 > c2) { if (who == "answer") quitf(_fail, "Jury answer has invalid rectangle order"); quitf(_wa, "Invalid rectangle order: r1 <= r2 and c1 <= c2 are required"); } return {r1 - 1, c1 - 1, r2 - 1, c2 - 1}; } 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> a(n, vector(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { a[i][j] = inf.readInt(); } } Rect jury = readRect(ans, n, m, "answer"); Rect part = readRect(ouf, n, m, "output"); long long opt = scoreRect(a, jury); long long got = scoreRect(a, part); if (2LL * got < opt) { quitf( _wa, "Test case %d: rectangle score is %lld, but at least ceil(%lld / 2) is required", tc, got, opt ); } } ouf.seekEof(); quitf(_ok, "All rectangles are valid 1/2-approximations"); }39:T81d,#include "testlib.h" #include using namespace std; struct OutputSet { int k; vector vertices; }; OutputSet readSet(InStream &stream, int n, const string &who) { int k = stream.readInt(1, n, (who + ".k").c_str()); vector vertices(k); vector seen(n + 1, 0); for (int i = 0; i < k; i++) { int v = stream.readInt(1, n, (who + ".vertex").c_str()); if (seen[v]) { if (who == "answer") quitf(_fail, "Jury answer contains vertex %d more than once", v); quitf(_wa, "Vertex %d appears more than once", v); } seen[v] = 1; vertices[i] = v; } return {k, vertices}; } long long countInternalEdges(int n, const vector> &edges, const vector &vertices) { vector in(n + 1, 0); for (int v : vertices) in[v] = 1; long long cnt = 0; for (auto [u, v] : edges) { if (in[u] && in[v]) cnt++; } return cnt; } 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> edges(m); for (auto &[u, v] : edges) { u = inf.readInt(); v = inf.readInt(); } OutputSet jury = readSet(ans, n, "answer"); OutputSet part = readSet(ouf, n, "output"); long long juryEdges = countInternalEdges(n, edges, jury.vertices); long long partEdges = countInternalEdges(n, edges, part.vertices); // partEdges / part.k >= (juryEdges / jury.k) / 2 __int128 lhs = (__int128)2 * partEdges * jury.k; __int128 rhs = (__int128)juryEdges * part.k; if (lhs < rhs) { quitf(_wa, "Test case %d: chosen density is %lld/%d, but at least half of jury density %lld/%d is required", tc, partEdges, part.k, juryEdges, jury.k); } } ouf.seekEof(); quitf(_ok, "All chosen sets are valid 1/2-approximations"); } 3a:T7c1,#include "testlib.h" #include using namespace std; int bfsDistance(const vector> &adj, int s, int t) { int n = (int)adj.size() - 1; vector dist(n + 1, -1), q(n); int head = 0, tail = 0; dist[s] = 0; q[tail++] = s; while (head < tail) { int v = q[head++]; if (v == t) return dist[v]; for (int to : adj[v]) { if (dist[to] == -1) { dist[to] = dist[v] + 1; q[tail++] = to; } } } return -1; } pair readPair(InStream &stream, int n, const string &name) { int a = stream.readInt(1, n, (name + ".a").c_str()); int b = stream.readInt(1, n, (name + ".b").c_str()); return {a, b}; } 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); for (int i = 0; i < m; i++) { int u = inf.readInt(); int v = inf.readInt(); adj[u].push_back(v); } auto jury = readPair(ans, n, "answer"); auto part = readPair(ouf, n, "output"); int juryDist = bfsDistance(adj, jury.first, jury.second); if (juryDist < 0) { quitf(_fail, "Jury pair is unreachable in test case %d", tc); } int partDist = bfsDistance(adj, part.first, part.second); if (partDist < 0) { quitf(_wa, "Test case %d: there is no directed path from %d to %d", tc, part.first, part.second); } if (2LL * partDist < juryDist) { quitf( _wa, "Test case %d: distance is %d, but at least ceil(%d / 2) is required", tc, partDist, juryDist ); } } ouf.seekEof(); quitf(_ok, "All pairs are valid 1/2-approximations"); } 3b:T97e,#include "testlib.h" #include using namespace std; struct EdgeInput { int u, v; }; vector readSet(InStream &stream, int n, const string &who) { int k = stream.readInt(0, n, (who + ".k").c_str()); vector vertices(k); vector used(n + 1, 0); for (int i = 0; i < k; i++) { int x = stream.readInt(1, n, (who + ".vertex").c_str()); if (used[x]) { if (who == "answer") quitf(_fail, "Jury answer contains a repeated vertex"); quitf(_wa, "Vertex %d appears more than once", x); } used[x] = 1; vertices[i] = x; } return vertices; } long long checkCoverAndWeight( const vector &chosen, const vector &w, const vector &edges, const string &who ) { int n = (int)w.size() - 1; vector used(n + 1, 0); long long total = 0; for (int x : chosen) { used[x] = 1; total += w[x]; } for (const auto &e : edges) { if (!used[e.u] && !used[e.v]) { if (who == "answer") { quitf(_fail, "Jury answer does not cover edge (%d, %d)", e.u, e.v); } quitf(_wa, "Edge (%d, %d) is not covered", e.u, e.v); } } return total; } int main(int argc, char *argv[]) { registerTestlibCmd(argc, argv); int T = inf.readInt(); for (int tc = 1; tc <= T; tc++) { int L = inf.readInt(); int R = inf.readInt(); int m = inf.readInt(); int n = L + R; vector w(n + 1); for (int i = 1; i <= n; i++) w[i] = inf.readLong(); vector edges(m); for (int i = 0; i < m; i++) { edges[i].u = inf.readInt(); edges[i].v = inf.readInt(); } vector jury = readSet(ans, n, "answer"); vector part = readSet(ouf, n, "output"); long long juryWeight = checkCoverAndWeight(jury, w, edges, "answer"); long long partWeight = checkCoverAndWeight(part, w, edges, "output"); if (partWeight > 2LL * juryWeight) { quitf( _wa, "Test case %d: output weight is %lld, but it must be at most %lld", tc, partWeight, 2LL * juryWeight ); } } ouf.seekEof(); quitf(_ok, "All covers are valid 2-approximations"); } 3c:T6dd,#include "testlib.h" #include using namespace std; vector readPermutation(InStream &stream, int n, const string &who) { vector p(n + 1); vector seen(n + 1, 0); for (int i = 1; i <= n; i++) { p[i] = stream.readInt(1, n, (who + ".p_i").c_str()); if (seen[p[i]]) { if (who == "answer") quitf(_fail, "Jury answer is not a permutation"); quitf(_wa, "The output is not a permutation: job %d appears more than once", p[i]); } seen[p[i]] = 1; } return p; } long long scorePermutation(const vector &p, const vector> &a) { int n = (int)p.size() - 1; long long score = 0; for (int i = 1; i <= n; i++) score += a[i][p[i]]; return score; } int main(int argc, char *argv[]) { registerTestlibCmd(argc, argv); int T = inf.readInt(); for (int tc = 1; tc <= T; tc++) { int n = inf.readInt(); vector> a(n + 1, vector(n + 1)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { a[i][j] = inf.readInt(); } } vector jury = readPermutation(ans, n, "answer"); vector part = readPermutation(ouf, n, "output"); long long juryScore = scorePermutation(jury, a); long long partScore = scorePermutation(part, a); if (2LL * partScore < juryScore) { quitf( _wa, "Test case %d: output score is %lld, but at least ceil(%lld / 2) is required", tc, partScore, juryScore ); } } ouf.seekEof(); quitf(_ok, "All assignments are valid 1/2-approximations"); } 3d:T478,#include "testlib.h" #include using namespace std; int main(int argc, char *argv[]) { registerTestlibCmd(argc, argv); int T = inf.readInt(); for (int tc = 1; tc <= T; tc++) { int n = inf.readInt(); long long W = inf.readLong(); vector w(n + 1); for (int i = 1; i <= n; i++) w[i] = inf.readLong(); int k = ouf.readInt(0, n, "k"); vector used(n + 1, 0); long long sum = 0; for (int i = 0; i < k; i++) { int id = ouf.readInt(1, n, "index"); if (used[id]) quitf(_wa, "Test case %d: index %d appears more than once", tc, id); used[id] = 1; sum += w[id]; if (sum > W) { quitf(_wa, "Test case %d: chosen total weight is %lld, which exceeds W = %lld", tc, sum, W); } } if (10LL * sum < 9LL * W) { quitf(_wa, "Test case %d: chosen total weight is %lld, but at least 90%% of W = %lld is required", tc, sum, W); } } ouf.seekEof(); quitf(_ok, "All subsets have total weight between 90%% of W and W"); } 1b:["$","div",null,{"children":[["$","$L36",null,{"contestId":"6a3d7855461635d759bba3b1","contestNumber":1012,"contestUrlId":"1012","initialIsRegistered":false}],["$","$L37",null,{"contest":{"contestNumber":1012,"title":"Testing Approx Problems","startDate":"2026-06-24T18:49:57.084Z","endDate":"2026-10-03T18:49:57.084Z","urlSlug":"$undefined","problemDisplay":"letters","requiresPremium":false,"lobbyProblemsCount":5,"isProblemSet":false,"contestType":"cp","adminOnly":false,"isWeeklyChallenge":false,"weekNumber":"$undefined","ratedMaxTier":"$undefined","announcements":[]},"problems":[{"_id":"6a3dcdbdab7ab0e77979616e","contestId":"6a3d7855461635d759bba3b1","slug":"2d-banner","title":"2D Banner","description":"You are given a grid with $n$ rows and $m$ columns. The cell in row $i$ and column $j$ has height $a_{i,j}$.\n\nYou want to place a rectangular banner on the grid. A banner is determined by four integers $r_1, c_1, r_2, c_2$ such that $1 \\le r_1 \\le r_2 \\le n$ and $1 \\le c_1 \\le c_2 \\le m$.\n\nThe score of this banner is:\n\n$\\min(a_{i,j}) \\times (r_2-r_1+1) \\times (c_2-c_1+1)$\n\nwhere the minimum is taken over all cells $(i,j)$ satisfying $r_1 \\le i \\le r_2$ and $c_1 \\le j \\le c_2$.\n\nLet $OPT$ be the maximum possible score of a banner.\n\nYou do not need to find an optimal banner. You only need to output any banner whose score is at least half of $OPT$.\n\nIn other words, if the score of your banner is $S$, your output is accepted if $2 \\times S \\ge OPT$.","constraints":"- $1 \\le t \\le 5$\n- $1 \\le n,m \\le 800$\n- The sum of $n \\times m$ over all test cases is at most $500000$\n- $1 \\le a_{i,j} \\le 10^6$","difficulty":"medium","order":1,"label":"$undefined","releaseDay":"$undefined","points":"$undefined","vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"1\n8 10\n3 4 2 5 1 4 3 2 5 1\n2 5 20 20 20 20 20 3 4 2\n4 1 20 20 20 20 20 5 2 3\n5 3 20 20 20 20 20 4 1 5\n1 2 20 20 20 20 20 3 5 4\n4 5 2 1 3 5 2 4 3 1\n2 3 5 4 1 2 5 3 4 2\n5 1 4 3 2 1 4 5 2 3\n","expectedOutput":"2 3 4 7","isSample":true,"hidden":false,"explanation":"The chosen banner covers rows $2$ to $4$ and columns $3$ to $7$.\n\nAll cells inside it have height $20$, and its area is $3 \\times 5 = 15$, so its score is $20 \\times 15 = 300$.\n\nThe rectangle from row $2$ to row $5$ and column $3$ to column $7$ has score $20 \\times 20 = 400$, so the shown output is not optimal. Still, a score of $300$ is enough because it is at least half of the optimal score.","displayInput":"1\n`\n8 10\n3 4 2 5 1 4 3 2 5 1\n2 5 20 20 20 20 20 3 4 2\n4 1 20 20 20 20 20 5 2 3\n5 3 20 20 20 20 20 4 1 5\n1 2 20 20 20 20 20 3 5 4\n4 5 2 1 3 5 2 4 3 1\n2 3 5 4 1 2 5 3 4 2\n5 1 4 3 2 1 4 5 2 3"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n\n$$\n\\left.\n\\begin{array}{l}\nn \\quad m \\\\\na_{1,1} \\quad a_{1,2} \\quad \\cdots \\quad a_{1,m} \\\\\na_{2,1} \\quad a_{2,2} \\quad \\cdots \\quad a_{2,m} \\\\\n\\vdots \\\\\na_{n,1} \\quad a_{n,2} \\quad \\cdots \\quad a_{n,m}\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"For each test case, output four integers $r_1, c_1, r_2, c_2$, describing the banner you choose.\n\nThe output must satisfy $1 \\le r_1 \\le r_2 \\le n$ and $1 \\le c_1 \\le c_2 \\le m$.\n\nIf the score of your banner is $S$, it must satisfy $2 \\times S \\ge OPT$.\n\nThe output format is:\n\n$$\n\\left.\n\\begin{array}{l}\nr_1 \\quad c_1 \\quad r_2 \\quad c_2\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"custom","sourceCode":"$38"},"solvedCount":0,"attemptedCount":0,"tags":"$undefined","learnPages":"$undefined","hasLearnContent":false,"likeCount":0,"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":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-06-26T00:54:21.146Z","updatedAt":"2026-07-14T11:13:04.162Z"},{"_id":"6a4520c61453ed1ea5b8b183","contestId":"6a3d7855461635d759bba3b1","slug":"dense-enough","title":"Dense Enough","description":"You are given a simple undirected graph with $n$ vertices and $m$ edges.\n\nFor a non-empty set of vertices $S$, define its score as:\n\n$\\frac{e(S)}{|S|}$\n\nwhere $e(S)$ is the number of edges with both endpoints inside $S$.\n\nLet $OPT$ be the maximum possible score over all non-empty sets of vertices.\n\nYou do not need to find an optimal set. You only need to output any non-empty set of vertices whose score is at least half of $OPT$.\n\nIn other words, if your chosen set is $S$, your output is accepted if:\n\n$2 \\times \\frac{e(S)}{|S|} \\ge OPT$","constraints":"- $1 \\le t \\le 5$\n- $1 \\le n \\le 1000$\n- $0 \\le m \\le 50000$\n- The sum of $n$ over all test cases is at most $1000$\n- The sum of $m$ over all test cases is at most $50000$\n- The graph has no self-loops or multiple edges","difficulty":"medium","order":2,"label":"$undefined","releaseDay":"$undefined","points":"$undefined","vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"1\n6 7\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4\n5 6\n","expectedOutput":"3\n1 2 3\n","isSample":true,"hidden":false,"explanation":"The chosen set is $\\{1,2,3\\}$. It contains $3$ internal edges, so its score is $3/3=1$.\n\nThe set $\\{1,2,3,4\\}$ has $6$ internal edges and score $6/4$. Therefore the shown output is not optimal, but it is still good enough because $1$ is at least half of $6/4$.\n"}],"sampleCount":1,"inputFormat":"The input is given in the following format:\n\n$$\nt\n$$\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, output a non-empty set of vertices.\n\nFirst, output an integer $k$, the number of chosen vertices.\n\nThen output $k$ distinct integers $s_1, s_2, \\ldots, s_k$, the chosen vertices.\n\nThe output format is:\n\n$$\n\\left.\n\\begin{array}{l}\nk \\\\\ns_1 \\quad s_2 \\quad \\cdots \\quad s_k\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"custom","sourceCode":"$39"},"solvedCount":0,"attemptedCount":0,"tags":"$undefined","learnPages":"$undefined","hasLearnContent":true,"likeCount":0,"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":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-07-01T14:14:30.177Z","updatedAt":"2026-09-06T02:58:47.519Z"},{"_id":"6a4524d2d0ff48b88ade58d8","contestId":"6a3d7855461635d759bba3b1","slug":"far-enough","title":"Far Enough","description":"You are given a strongly connected directed graph with $n$ vertices and $m$ edges.\n\nFor two vertices $u$ and $v$, let $dist(u,v)$ be the minimum number of edges in a directed path from $u$ to $v$.\n\nThe directed diameter of the graph is the maximum value of $dist(u,v)$ over all ordered pairs of vertices $(u,v)$.\n\nYou do not need to find the directed diameter exactly. You only need to output an ordered pair of vertices whose distance is at least half of the directed diameter.\n\nMore formally, let $D$ be the directed diameter of the graph. You have to output two vertices $a$ and $b$ such that $2 \\times dist(a,b) \\ge D$.","constraints":"- $1 \\le t \\le 5$\n- $2 \\le n \\le 6000$\n- $n \\le m \\le 100000$\n- The sum of $n$ over all test cases is at most $6000$\n- The sum of $m$ over all test cases is at most $100000$\n- The graph is strongly connected\n- There are no self-loops or multiple directed edges","difficulty":"medium","order":3,"label":"$undefined","releaseDay":"$undefined","points":"$undefined","vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"1\n6 7\n1 2\n2 3\n3 4\n4 5\n5 6\n6 1\n1 4\n","expectedOutput":"1 6\n","isSample":true,"hidden":false,"explanation":"There is a directed path from $1$ to $6$ with length $3$: $1 \\to 4 \\to 5 \\to 6$.\n\nThe pair $(2,1)$ has distance $5$, so the shown output is not optimal. Still, the shown distance is enough because $2 \\times 3 \\ge 5$.\n"}],"sampleCount":1,"inputFormat":"The input is given in the following format:\n\n$$\nt\n$$\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$$\n\nEach edge is directed from $u_i$ to $v_i$.","outputFormat":"For each test case, output two integers $a$ and $b$, describing the ordered pair of vertices you choose.\n\nIf the directed diameter of the graph is $D$, your output must satisfy $2 \\times dist(a,b) \\ge D$.\n\nThe output format is:\n\n$$\n\\left.\n\\begin{array}{l}\na \\quad b\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"custom","sourceCode":"$3a"},"solvedCount":0,"attemptedCount":0,"tags":"$undefined","learnPages":"$undefined","hasLearnContent":true,"likeCount":0,"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":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-07-01T14:31:46.883Z","updatedAt":"2026-09-06T02:58:47.637Z"},{"_id":"6a452851d0ff48b88ade58da","contestId":"6a3d7855461635d759bba3b1","slug":"light-cover","title":"Light Cover","description":"You are given a bipartite graph. The graph has $L$ vertices on the left side and $R$ vertices on the right side.\n\nThe vertices are numbered from $1$ to $L+R$. Vertices $1,2,\\ldots,L$ are on the left side, and vertices $L+1,L+2,\\ldots,L+R$ are on the right side.\n\nEach vertex $i$ has a positive weight $w_i$.\n\nA set of vertices is called a cover if every edge has at least one endpoint in the set.\n\nThe weight of a cover is the sum of weights of its vertices. Let $OPT$ be the minimum possible weight of a cover.\n\nYou do not need to find an optimal cover. You only need to output any cover whose weight is at most twice $OPT$.\n\nIn other words, if the weight of your cover is $W$, your output is accepted if $W \\le 2 \\times OPT$.","constraints":"- $1 \\le t \\le 5$\n- $1 \\le L,R$\n- $L+R \\le 10^5$\n- $0 \\le m \\le 5 \\times 10^5$\n- The sum of $L+R$ over all test cases is at most $10^5$\n- The sum of $m$ over all test cases is at most $5 \\times 10^5$\n- $1 \\le w_i \\le 10^9$\n- Each edge connects one left vertex to one right vertex\n- There are no duplicate edges","difficulty":"medium","order":4,"label":"$undefined","releaseDay":"$undefined","points":"$undefined","vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"1\n3 3 5\n4 3 6 2 5 4\n1 4\n1 5\n2 5\n3 5\n3 6\n","expectedOutput":"3\n1 2 3\n","isSample":true,"hidden":false,"explanation":"The chosen vertices cover all edges: every edge has its left endpoint among $1,2,3$.\n\nThe total weight is $4+3+6=13$.\n\nThe minimum possible cover weight is $11$. For example, $\\{4,5,6\\}$ is a cover with total weight $2+5+4=11$. The shown output is not optimal, but $13 \\le 2 \\times 11$.\n"}],"sampleCount":1,"inputFormat":"The input is given in the following format:\n\n$$\nt\n$$\n\n$$\n\\left.\n\\begin{array}{l}\nL \\quad R \\quad m \\\\\nw_1 \\quad w_2 \\quad \\cdots \\quad w_{L+R} \\\\\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$$\n\nFor each edge, $1 \\le u_i \\le L$ and $L+1 \\le v_i \\le L+R$.","outputFormat":"For each test case, first output an integer $k$, the number of vertices in your cover.\n\nThen output $k$ distinct integers $x_1,x_2,\\ldots,x_k$, the vertices you choose.\n\nThe chosen vertices must form a cover. If the weight of your cover is $W$, it must satisfy $W \\le 2 \\times OPT$.\n\nThe output format is:\n\n$$\n\\left.\n\\begin{array}{l}\nk \\\\\nx_1 \\quad x_2 \\quad \\cdots \\quad x_k\n\\end{array}\n\\right\\} \\times t\n$$\n\nIf $k=0$, the second line for that test case may be empty.","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"custom","sourceCode":"$3b"},"solvedCount":0,"attemptedCount":0,"tags":"$undefined","learnPages":"$undefined","hasLearnContent":true,"likeCount":0,"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":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-07-01T14:46:41.432Z","updatedAt":"2026-09-06T02:58:47.752Z"},{"_id":"6a452ec4d0ff48b88ade58dc","contestId":"6a3d7855461635d759bba3b1","slug":"almost-assignment","title":"Almost Assignment","description":"You are given $n$ workers and $n$ jobs.\n\nIf worker $i$ is assigned to job $j$, you gain profit $a_{i,j}$.\n\nYou must assign each worker to exactly one job, and each job to exactly one worker. In other words, you must choose a permutation $p_1,p_2,\\ldots,p_n$, where worker $i$ is assigned to job $p_i$.\n\nThe score of an assignment is:\n\n$\\sum_{i=1}^{n} a_{i,p_i}$\n\nLet $OPT$ be the maximum possible score of an assignment.\n\nYou do not need to find an optimal assignment. You only need to output any assignment whose score is at least half of $OPT$.\n\nIn other words, if the score of your assignment is $S$, your output is accepted if $2 \\times S \\ge OPT$.","constraints":"- $1 \\le t \\le 3$\n- $1 \\le n \\le 900$\n- The sum of $n^2$ over all test cases is at most $900000$\n- $1 \\le a_{i,j} \\le 10^9$","difficulty":"medium","order":5,"label":"$undefined","releaseDay":"$undefined","points":"$undefined","vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"1\n5\n10 8 7 6 5\n9 1 1 1 1\n8 7 20 3 2\n7 6 5 18 4\n6 5 4 3 16\n","expectedOutput":"1 2 3 4 5\n","isSample":true,"hidden":false,"explanation":"The shown assignment gives jobs $1,2,3,4,5$ to workers $1,2,3,4,5$ respectively.\n\nIts score is $10+1+20+18+16=65$.\n\nThis is not optimal: assigning jobs $2,1,3,4,5$ gives score $8+9+20+18+16=71$. Still, the shown assignment is accepted because $2 \\times 65 \\ge 71$.\n"}],"sampleCount":1,"inputFormat":"The input is given in the following format:\n\n$$\nt\n$$\n\n$$\n\\left.\n\\begin{array}{l}\nn \\\\\na_{1,1} \\quad a_{1,2} \\quad \\cdots \\quad a_{1,n} \\\\\na_{2,1} \\quad a_{2,2} \\quad \\cdots \\quad a_{2,n} \\\\\n\\vdots \\\\\na_{n,1} \\quad a_{n,2} \\quad \\cdots \\quad a_{n,n}\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"For each test case, output a permutation $p_1,p_2,\\ldots,p_n$.\n\nThis means each integer from $1$ to $n$ must appear exactly once. Worker $i$ will be assigned to job $p_i$.\n\nIf the score of your assignment is $S$, it must satisfy $2 \\times S \\ge OPT$.\n\nThe output format is:\n\n$$\n\\left.\n\\begin{array}{l}\np_1 \\quad p_2 \\quad \\cdots \\quad p_n\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"custom","sourceCode":"$3c"},"solvedCount":0,"attemptedCount":0,"tags":"$undefined","learnPages":"$undefined","hasLearnContent":true,"likeCount":0,"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":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-07-01T15:14:12.853Z","updatedAt":"2026-09-06T02:58:47.864Z"},{"_id":"6a45340bd0ff48b88ade58de","contestId":"6a3d7855461635d759bba3b1","slug":"almost-full","title":"Full Enough (Hard Version)","description":"You are given $n$ stones. The weight of stone $i$ is $w_i$.\n\nYou have a bag with capacity $W$. You may choose any subset of stones whose total weight is at most $W$.\n\nThe score of your choice is the total weight of the chosen stones.\n\nLet $OPT$ be the maximum possible score.\n\nYou do not need to find an optimal subset. You only need to output any subset whose score is at least $90\\%$ of $OPT$.\n\nIn other words, if the score of your subset is $S$, your output is accepted if $10 \\times S \\ge 9 \\times OPT$.","constraints":"- $1 \\le t \\le 3$\n- $1 \\le n \\le 750$\n- $1 \\le W \\le 3 \\times 10^7$\n- $1 \\le w_i \\le W$\n- The sum of $n$ over all test cases is at most $750$","difficulty":"medium","order":6,"label":"$undefined","releaseDay":"$undefined","points":"$undefined","vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"1\n8 100\n45 45 60 40 30 20 15 5\n","expectedOutput":"2\n1 2\n","isSample":true,"hidden":false,"explanation":"The chosen stones have total weight $45+45=90$.\n\nThis does not fill the bag exactly, but it is still valid because $90$ is exactly $90\\%$ of $100$ and does not exceed the capacity.\n"}],"sampleCount":1,"inputFormat":"The input is given in the following format:\n\n$$\nt\n$$\n\n$$\n\\left.\n\\begin{array}{l}\nn \\quad W \\\\\nw_1 \\quad w_2 \\quad \\cdots \\quad w_n\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"For each test case, first output an integer $k$, the number of chosen stones.\n\nThen output $k$ distinct integers $i_1, i_2, \\ldots, i_k$, the indices of the chosen stones.\n\nThe total weight of the chosen stones must not exceed $W$.\n\nIf the score of your subset is $S$, it must satisfy $10 \\times S \\ge 9 \\times OPT$.\n\nThe output format is:\n\n$$\n\\left.\n\\begin{array}{l}\nk \\\\\ni_1 \\quad i_2 \\quad \\cdots \\quad i_k\n\\end{array}\n\\right\\} \\times t\n$$\n\nIf $k=0$, the second line for that test case should be empty.","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"custom","sourceCode":"$3d"},"solvedCount":0,"attemptedCount":0,"tags":"$undefined","learnPages":"$undefined","hasLearnContent":true,"likeCount":0,"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":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-07-01T15:36:43.820Z","updatedAt":"2026-09-06T02:58:47.984Z"}],"contestId":"6a3d7855461635d759bba3b1","contestUrlId":"1012","isAdmin":false,"isTester":false,"isStarted":true,"isRegistered":false,"canRegister":true,"problemStatusMap":{},"isPremiumBlocked":false,"sponsorshipSnapshot":"$1a:props:children:1:props:children:0:props:sponsorshipSnapshot","recentRoundParticipantCounts":[92,108,96],"participationMode":null,"virtualStartTime":null,"contestDurationMs":8726400000}]]}]