{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch2\u003eProblem C\n\u003c/h2\u003e\n\n\u003cp\u003e\nYou are playing a game with your elder brother.\n\u003c/p\u003e\n\n\u003cp\u003e\nFirst, a number of circles and arrows connecting some pairs of the circles are drawn on the ground. Two of the circles are marked as the \u003ci\u003estart circle\u003c/i\u003e and the \u003ci\u003egoal circle\u003c/i\u003e.\n\u003c/p\u003e\n\n\u003cp\u003e\nAt the start of the game, you are on the start circle. In each \u003ci\u003eturn\u003c/i\u003e of the game, your brother tells you a number, and you have to take that number of \u003ci\u003esteps\u003c/i\u003e. At each step, you choose one of the arrows outgoing from the circle you are on, and move to the circle the arrow is heading to. You can visit the same circle or use the same arrow any number of times.\n\u003c/p\u003e\n\n\u003cp\u003e\nYour aim is to stop on the goal circle after the fewest possible turns, while your brother\u0027s aim is to prevent it as long as possible. Note that, in each single turn, you \u003ci\u003emust\u003c/i\u003e take the exact number of steps your brother tells you. Even when you visit the goal circle during a turn, you have to leave it if more steps are to be taken.\n\u003c/p\u003e\n\n\u003cp\u003e\nIf you reach a circle with no outgoing arrows before completing all the steps, then you lose the game. You also have to note that, your brother may be able to repeat turns forever, not allowing you to stop after any of them.\n\u003c/p\u003e\n\n\u003cp\u003e\nYour brother, mean but not too selfish, thought that being allowed to choose arbitrary numbers is not fair. So, he decided to declare three numbers at the start of the game and to use only those numbers.\n\u003c/p\u003e\n\n\u003cp\u003e\nYour task now is, given the configuration of circles and arrows, and the three numbers declared, to compute the smallest possible number of turns within which you can always finish the game, no matter how your brother chooses the numbers.\n\u003c/p\u003e\n\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\n\u003cp\u003e\nThe input consists of a single test case, formatted as follows.\u003cbr\u003e\n\u003cbr\u003e\n\n$n$ $m$ $a$ $b$ $c$\u003cbr\u003e\n$u_1$ $v_1$\u003cbr\u003e\n...\u003cbr\u003e\n$u_m$ $v_m$\u003cbr\u003e\n\u003cbr\u003e\n\n\nAll numbers in a test case are integers. $n$ is the number of circles $(2 \\leq n \\leq 50)$. Circles are numbered 1 through $n$. The start and goal circles are numbered 1 and $n$, respectively. $m$ is the number of arrows $(0 \\leq m \\leq n(n - 1))$. $a$, $b$, and $c$ are the three numbers your brother declared $(1 \\leq a, b, c \\leq 100)$. The pair, $u_i$ and $v_i$, means that there is an arrow from the circle $u_i$ to the circle $v_i$. It is ensured that $u_i \\ne v_i$ for all $i$, and $u_i \\ne u_j$ or $v_i \\ne v_j$ if $i \\ne j$.\n\u003c/p\u003e\n\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\n\u003cp\u003e\nPrint the smallest possible number of turns within which you can always finish the game. Print \u003cspan\u003eIMPOSSIBLE\u003c/span\u003e if your brother can prevent you from reaching the goal, by either making you repeat the turns forever or leading you to a circle without outgoing arrows.\n\u003c/p\u003e\n\n\n\n\u003ch3\u003eSample Input 1\u003c/h3\u003e\n\n\u003cpre\u003e3 3 1 2 4\n1 2\n2 3\n3 1\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 1\u003c/h3\u003e\n\n\u003cpre\u003eIMPOSSIBLE\u003c/pre\u003e\n\n\n\n\u003ch3\u003eSample Input 2\u003c/h3\u003e\n\n\u003cpre\u003e8 12 1 2 3\n1 2\n2 3\n1 4\n2 4\n3 4\n1 5\n5 8\n4 6\n6 7\n4 8\n6 8\n7 8\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 2\u003c/h3\u003e\n\n\u003cpre\u003e2\u003c/pre\u003e\n\n\u003cp\u003e\nFor Sample Input 1, your brother may choose 1 first, then 2, and repeat these forever. Then you can never finish.\n\u003c/p\u003e\n\n\u003cp\u003e\nFor Sample Input 2 (Figure C.1), if your brother chooses 2 or 3, you can finish with a single turn. If he chooses 1, you will have three options.\n\u003c/p\u003e\n\n\u003cul\u003e\n\u003cli\u003e Move to the circle 5. This is a bad idea: Your brother may then choose 2 or 3 and make you lose.\u003c/li\u003e\n\u003cli\u003e Move to the circle 4. This is the best choice: From the circle 4, no matter any of 1, 2, or 3 your brother chooses in the next turn, you can finish immediately.\u003c/li\u003e\n\u003cli\u003eMove to the circle 2. This is not optimal for you. If your brother chooses 1 in the next turn, you cannot finish yet. It will take three or more turns in total.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003e\nIn summary, no matter how your brother acts, you can finish within two turns. Thus the answer is 2.\n\u003c/p\u003e\n\n\u003ccenter\u003e\n\u003cimg src\u003d\"CDN_BASE_URL/da1e8231a3b8c1e960524cd565fe7bde?v\u003d1714780289\"\u003e\u003cbr\u003e\n\u003cp\u003eFigure C.1. Sample Input 2\u003c/p\u003e\n\u003c/center\u003e\n"}}]}