{"trustable":false,"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":"\u003cstyle type\u003d\u0027text/css\u0027\u003e .input, .output {border: 1px solid #888888;} .output {margin-bottom:1em;position:relative;top:-1px;} .output pre,.input pre {background-color:#EFEFEF;line-height:1.25em;margin:0;padding:0.25em;} .title {background-color:#FFFFFF;border-bottom: 1px solid #888888;font-family:arial;font-weight:bold;padding:0.25em;} \u003c/style\u003e \u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027]], displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027]]}\n });\n \u003c/script\u003e\n \u003cscript type\u003d\"text/javascript\" async\n src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\"\u003e\n \u003c/script\u003e\n\u003cp\u003e给你一个3*n个顶点m条边的图. 你需要找出大小为n的匹配集或点的独立集, \u003c/p\u003e\n\u003cp\u003e在一个边的集合里如果任意两条边的顶点都不同,则称为匹配集\u003c/p\u003e\n\u003cp\u003e在一个点的集合里如果任意两点的之间都没有边,则称为点独立集\u003c/p\u003e\n\u003cp\u003e最大匹配可以用二分图匹配求出,而二分图的最大独立集等于顶点数减去最大匹配\u003c/p\u003e\n\u003cpre\u003e二分图:对于一个图G\u003d(V,E),若能将其点集分为两个互不相交的两个子集X、Y,使得X∩Y\u003d∅,且对于G的边集V,若其所有边的顶点全部一侧属于X,一侧属于Y,则称图G为一个二分图。\n二分图判定:无奇环,可以用黑白染色判断。\n匹配: 对于一个二分图G的子图M,若M的边集E的的任意两条边都不连接同一个顶点,则称M为G的一个匹配。\n最大匹配:若二分图G的一个匹配M为其边数最多的匹配,则称M为G的最大匹配。\n最大匹配的求法:匈牙利算法;网络流:源点到左侧点,左侧点到右侧点,右侧点到汇点间都建流量为1的边,最大流即为最大匹配。\n\u003c/pre\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e第一行输入T,代表T个样例\u003c/p\u003e\n\u003cp\u003e在每个样例的第一行输入n和m (1≤n≤1e5, 0≤m≤5⋅1e5).\u003c/p\u003e\n\u003cp\u003e随后m行 每行输入 ui,vi 代表一条边 (1≤vi,ui≤3⋅n)\u003c/p\u003e\n\u003cp\u003e输入保证不存在重边和自环\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e按以下格式输出答案\u003c/p\u003e\n\u003cp\u003e如果可以找到大小为n的匹配集,在第一行输出\"Matching\" 在第二行输出n个数字代表集合中边的序号,边的序号按输入顺序从1到m.\u003c/p\u003e\n\u003cp\u003e如果可以找到大小为n的点独立集,在第一行输出\"IndSet\" 在第二行输出n个数字代表集合中顶点的序号,点的序号从1到3*n.\u003c/p\u003e\n\u003cp\u003e如果图中不存在这两种集合,输出“Impossible\" .\u003c/p\u003e\n\u003cp\u003e你可以按任意顺序输出边或者点的序号\u003c/p\u003e\n\u003cp\u003e如果有多种情况,输出任意一种即可,即如果同时满足两种集合,输出两者中任一皆可\u003c/p\u003e"}},{"title":"Example","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e4\n1 2\n1 3\n1 2\n1 2\n1 3\n1 2\n2 5\n1 2\n3 1\n1 4\n5 1\n1 6\n2 15\n1 2\n1 3\n1 4\n1 5\n1 6\n2 3\n2 4\n2 5\n2 6\n3 4\n3 5\n3 6\n4 5\n4 6\n5 6\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003eMatching\n2\nIndSet\n1\nIndSet\n2 4\nMatching\n1 15\n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003e前两个图是相同的,并且都有大小为1的匹配集和大小为1的独立集合。任何这些匹配和独立集都是正确答案。\u003c/p\u003e\n\u003cp\u003e第三个图没有大小为2的匹配集,但是有一个大小为2的独立集合。此外,还有一个大小为5的独立集合:2 3 4 5 6。但是,这样的答案是不正确的,因为要求你查找一个大小为n的独立集合(或匹配)\u003c/p\u003e\n\u003cp\u003e第四个图没有大小为2的独立集合,但是有大小为2的匹配集合。\u003c/p\u003e"}}]}