{"problem":{"name":"E. Dead-End Detector","description":{"content":"The council of your home town has decided to improve road sign placement, especially for dead ends. They have given you a road map, and you must determine where to put up signs to mark the dead ends. ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":5000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10251E"},"statements":[{"statement_type":"Markdown","content":"The council of your home town has decided to improve road sign placement, especially for dead ends. They have given you a road map, and you must determine where to put up signs to mark the dead ends. They want you to use as few signs as possible.\n\nThe road map is a collection of locations connected by two-way streets. The following rule describes how to obtain a complete placement of dead-end signs. Consider a street $S$ connecting a location $x$ with another location. The $x$-entrance of $S$ gets a dead-end sign if, after entering $S$ from $x$, it is not possible to come back to $x$ without making a U-turn. A U-turn is a 180-degree turn immediately reversing the direction.\n\nTo save costs, you have decided not to install redundant dead-end signs, as specified by the following rule. Consider a street $S$ with a dead-end sign at its $x$-entrance and another street $T$ with a dead-end sign at its $y$-entrance. If, after entering $S$ from $x$, it is possible to go to $y$ and enter $T$ without making a U-turn, the dead-end sign at the $y$-entrance of $T$ is redundant. See Figure E.1 for examples.\n\nFigure E.1: Illustration of sample inputs, indicating where non-redundant dead-end signs are placed. \n\nThe first line of input contains two integers $n$ and $m$, where $n$ ($1 <= n <= 5 dot.op 10^5$ ) is the number of locations and $m$ ($0 <= m <= 5 dot.op 10^5$) is the number of streets. Each of the following $m$ lines contains two integers $v$ and $w$ ($1 <= v < w <= n$) indicating that there is a two-way street connecting locations $v$ and $w$. All location pairs in the input are distinct.\n\nOn the first line, output $k$, the number of dead-end signs installed. On each of the next $k$ lines, output two integers $v$ and $w$ marking that a dead-end sign should be installed at the $v$-entrance of a street connecting locations $v$ and $w$. The lines describing dead-end signs must be sorted in ascending order of $v$-locations, breaking ties in ascending order of $w$-locations.\n\n## Input\n\nThe first line of input contains two integers $n$ and $m$, where $n$ ($1 <= n <= 5 dot.op 10^5$ ) is the number of locations and $m$ ($0 <= m <= 5 dot.op 10^5$) is the number of streets. Each of the following $m$ lines contains two integers $v$ and $w$ ($1 <= v < w <= n$) indicating that there is a two-way street connecting locations $v$ and $w$. All location pairs in the input are distinct.\n\n## Output\n\nOn the first line, output $k$, the number of dead-end signs installed. On each of the next $k$ lines, output two integers $v$ and $w$ marking that a dead-end sign should be installed at the $v$-entrance of a street connecting locations $v$ and $w$. The lines describing dead-end signs must be sorted in ascending order of $v$-locations, breaking ties in ascending order of $w$-locations.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ X \\in \\mathbb{Z} $ be the target number of delicious subrectangles.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 50 $  \n2. $ 1 \\le X \\le 7995051 $  \n3. Output dimensions $ N, M \\in \\mathbb{Z} $ such that $ 1 \\le N, M \\le 200 $  \n4. Sweetness values are nonnegative integers $ \\le 10^6 $  \n\n**Objective**  \nConstruct an $ N \\times M $ grid of nonnegative integers such that the total number of *delicious* $ 1 \\times K $ or $ K \\times 1 $ contiguous subrectangles (i.e., those with strictly increasing or strictly decreasing values along their single row or column) is exactly $ X $.  \n\nA $ 1 \\times K $ subrectangle (row segment) is delicious if its $ K $ values are strictly monotonic (increasing or decreasing).  \nA $ K \\times 1 $ subrectangle (column segment) is delicious if its $ K $ values are strictly monotonic (increasing or decreasing).  \n\nEach such segment of length $ \\ge 1 $ counts as one delicious subrectangle.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10251E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}