{"kind":"task","effective_mode":"full","benchmark":{"kind":"benchmark","effective_mode":"full","slug":"hlce","formal_name":"Humanity's Last Code Exam","introduction":"Humanity's Last Code Exam evaluates problem solving and code generation using ICPC World Finals and IOI problems. The project describes 235 problems; this import selects its public ICPC dataset of 146 problems.","introduction_ja":"","introduction_en":"","category":"Category not supplied","task_count":null,"acquisition_status":"Acquisition status not supplied","official_url":"https://humanity-s-last-code-exam.github.io/website/","indexing_mode":"noindex","profile":{"resources":[],"task_format":"","scoring":"","metric":"","size":"","answer_access":"","license":"","citation":"","maintainer":"","released":"","why_hard":"","related":[]}},"task_id":"cdbf7a62-be21-503c-9c37-7e46592407dc","task_key":"ICPC~2dWorld~2dFinals--examples--2019~5fE","task_revision_id":"3","upstream_id":"2019_E","short_description":"Dead-End Detector","config":"ICPC-World-Finals","split":"examples","body":"{\"platform\":\"atcoder\",\"question_content\":\"## Problem Statement\\n\\nThe council of your hometown 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\\n## Input\\n\\nThe first line of input contains two integers \\\\(n\\\\) and \\\\(m\\\\), where \\\\(n\\\\) (\\\\(1 \\\\leq n \\\\leq 5 \\\\times 10^5\\\\)) is the number of locations and \\\\(m\\\\) (\\\\(0 \\\\leq m \\\\leq 5 \\\\times 10^5\\\\)) is the number of streets. Each of the following \\\\(m\\\\) lines contains two integers \\\\(v\\\\) and \\\\(w\\\\) (\\\\(1 \\\\leq v < w \\\\leq 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## Sample Input 1\\n\\n```\\n6 5\\n1 2\\n1 3\\n2 3\\n4 5\\n5 6\\n```\\n\\n## Sample Output 1\\n\\n```\\n2\\n4 5\\n6 5\\n```\\n\\n## Sample Input 2\\n\\n```\\n8 8\\n1 2\\n1 3\\n2 3\\n3 4\\n1 5\\n1 6\\n6 7\\n6 8\\n```\\n\\n## Sample Output 2\\n\\n```\\n3\\n1 5\\n1 6\\n3 4\\n```\",\"question_title\":\"Dead-End Detector\"}","display_format":"text","language":"","answer_status":"published","assets":[],"source_url":"https://humanity-s-last-code-exam.github.io/website/","history":"initial import","indexing_mode":"noindex","subproblems":[],"grids":[]}