You are given a graph with 3⋅𝑛 vertices and 𝑚 edges. You are to find a matching of 𝑛 edges, or an independent set of 𝑛 vertices.

A set of edges is called a matching if no two edges share an endpoint.

A set of vertices is called an independent set if no two vertices are connected with an edge.

#### 链接 🔗

「CodeForces 1198C」 Matching vs Independent Set

#### 代码

const ll maxd = 4e5+10;
int main()
{
//    __IN;__OUT;
ll t;RLL(t);
while(t--)
{
ll n,m,x,y;RLL2(n,m);
V vis((3*n)+1,0),ans;
F(m)
{
RLL2(x,y);
if(!vis[x] && !vis[y])
{
vis[x] = vis[y] = 1;
ans.pb(i+1);
}
}

if(ans.size()>=n)
{
PS("Matching");
ll tot = 0;
for(auto x:ans) {
PLP(x);tot++;
if(tot == n) break;
}
}
else
{
PS("IndSet");
ll tot = 0;
FOR(i,1,3*n)
if(!vis[i])
{
PLP(i);tot++;
if (tot == n) break;
}
}
PN();
}
return 0;
}