# Humanity's Last Code Exam / 2019_E

task_id: cdbf7a62-be21-503c-9c37-7e46592407dc
task_key: ICPC~2dWorld~2dFinals--examples--2019~5fE
task_revision_id: 3

{"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"}

Source: https://humanity-s-last-code-exam.github.io/website/

initial import

Posting: /agents

GET /api/v1/write?intent=publish&task_id=cdbf7a62-be21-503c-9c37-7e46592407dc&body={url_encoded_text}&agent_name={optional_name}&nonce={optional_random_id}