{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eA long time ago in a galaxy far, far away, there was a group of knights who mastered the ancient power - the Force. To bring order and balance to the universe, the Force is divided into two categories that conflict with each other: the Jedi, who acts on the light side of the Force through non-attachment and arbitration, and the Sith, who uses the dark side through fear and aggression. \u003c/p\u003e\u003cp\u003eThere were $$$N$$$ knights who mastered the Force. Each knight could join either the light side or the dark side. When joining the light side, the knight possesses $$$L_i$$$ Force; when joining the dark side, the knight possesses $$$D_i$$$ Force.\u003c/p\u003e\u003cp\u003eTo maintain order and balance of the universe, the knights wanted to make the Force difference between the most powerful knight and the weakest knight as small as possible. To make things even tougher, some knights did not get along well, and they refused to join on the same side.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input gives the number of test cases, $$$T$$$ ($$$1 \\le T \\le 20$$$). $$$T$$$ test cases follow.\u003c/p\u003e\u003cp\u003eFor each test case, the first line contains two integers $$$N$$$ ($$$1 \\le N \\le 2 \\times 10^5$$$) and $$$M$$$ ($$$0 \\le M \\le 2 \\times 10^5$$$), where $$$N$$$ is the number of knights and $$$M$$$ is the number of knight pairs that didn\u0027t get along well.\u003c/p\u003e\u003cp\u003eThe next $$$M$$$ lines each contains two integers $$$x$$$ and $$$y$$$ ($$$1 \\le x \\neq y \\le N$$$), describing knight $$$x$$$ and knight $$$y$$$ didn\u0027t get along well.\u003c/p\u003e\u003cp\u003eThe following $$$N$$$ lines each contains two integers, $$$L_i$$$ and $$$D_i$$$ ($$$1 \\le L_i, D_i \\le 10^9$$$), representing the Force when the knight joined the light side and the dark side.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, output one line containing \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eCase x: y\u003c/span\u003e\", where \u003cspan class\u003d\"tex-font-style-tt\"\u003ex\u003c/span\u003e is the test case number (starting from $$$1$$$) and \u003cspan class\u003d\"tex-font-style-tt\"\u003ey\u003c/span\u003e is the minimum difference between the strongest knight and weakest knight, or \"IMPOSSIBLE\" (quotes for clarify) if it\u0027s impossible for the knights to pick side without violating the given constraints.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n3 1\n1 2\n1 2\n3 4\n5 6\n4 3\n1 2\n2 3\n1 3\n1 2\n3 4\n5 6\n7 8\n2 0\n2 1\n3 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 3\nCase 2: IMPOSSIBLE\nCase 3: 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eFor the case 1, let knight 1 join the dark side then let knight 2 and 3 join the light side, the power of each knight are 2, 3 and 5, and the answer should be $$$5 - 2 \u003d 3$$$.\u003c/p\u003e\u003cp\u003eFor the case 3, let both knights join the light side, the answer becomes $$$3 - 2 \u003d 1$$$.\u003c/p\u003e"}}]}