{"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\u003e最近,Pari 和 Arya 对 NP-Hard 问题进行了一些研究,他们发现“最小顶点覆盖”问题非常有趣。\u003c/p\u003e\u003cp\u003e假设给定图 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eG\u003c/i\u003e\u003c/span\u003e。如果其顶点的子集 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e 被称为该图的 \u003cspan class\u003d\"tex-font-style-underline\"\u003e顶点覆盖\u003c/span\u003e,那么对于每条边 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003euv\u003c/i\u003e\u003c/span\u003e,该集合中至少有一个端点与之相连,即 \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/1d019ea5a1aa43f3c1ec619f21277d03?v\u003d1711027433\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e 或 \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/6345cc83cb905811a1d776d2f59f1d52?v\u003d1711027433\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e(或两者都有)。\u003c/p\u003e\u003cp\u003ePari 和 Arya 在一场团队比赛中赢得了一张很棒的无向图作为奖品。现在他们需要将其分成两部分,但他们都希望自己的部分成为顶点覆盖。\u003c/p\u003e\u003cp\u003e他们同意把他们的图给你,你需要找到两个 \u003cspan class\u003d\"tex-font-style-bf\"\u003e不相交\u003c/span\u003e 的顶点子集 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e 和 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e,使得 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e 和 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e 都成为顶点覆盖,或者宣布不可能。每个顶点最多只能分配给其中的一个朋友(或者你甚至可以留给自己)。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入的第一行包含两个整数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e 和 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 100 000\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003em\u003c/i\u003e ≤ 100 000\u003c/span\u003e)— 分别表示奖品图中的顶点数和边数。\u003c/p\u003e\u003cp\u003e接下来的 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e 行中,每行包含一对整数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e 和 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e),表示图中的一条无向边连接 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e 和 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e。保证图中不包含自环或重边。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e如果无法按照 Pari 和 Arya 的期望将图分开,输出 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e\"(不带引号)。\u003c/p\u003e\u003cp\u003e如果存在两个不相交的顶点集,使得两个集合都是顶点覆盖,输出它们的描述。每个描述包含两行。第一行包含一个整数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e,表示该顶点覆盖中的顶点数,第二行包含 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e 个整数 — 顶点的索引。请注意,由于 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e ≥ 1\u003c/span\u003e 的原因,顶点覆盖不能为空。\u003c/p\u003e"}},{"title":"示例 1","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\u003e4 2\n1 2\n2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n2 \n2\n1 3 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"示例 2","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 3\n1 2\n2 3\n1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个示例中,你可以把顶点编号 \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e 给 Arya,把编号为 \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e 和 \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e 的顶点给 Pari,然后把编号为 \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e 的顶点留给自己(或者分给其他人,如果你愿意的话)。\u003c/p\u003e\u003cp\u003e在第二个示例中,无法满足 Pari 和 Arya 的要求。\u003c/p\u003e"}}]}