思维构造+匹配——cf1199E

#include<bits/stdc++.h>

using namespace std;
#define N 500005

struct Edge{int u,v;}e[N];
int n,m,f[N];
vector<int>ans;

int main(){
    int t;cin>>t;
    while(t--){
        ans.clear();
        scanf("%d%d",&n,&m);
        n*=3;
        for(int i=1;i<=n;i++)f[i]=0;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&e[i].u,&e[i].v);
            if(!f[e[i].u] && !f[e[i].v]){
                ans.push_back(i);
                f[e[i].v]=f[e[i].u]=1;    
            }
        }
        
        if(ans.size()>=n/3){
            puts("Matching");
            for(int i=0;i<n/3;i++)
                cout<<ans[i]<<" ";
        }
        else {
            puts("IndSet");
            int cnt=0;
            for(int i=1;i<=n;i++){
                if(!f[i]){
                    cout<<i<<" ";
                    cnt++;
                    if(cnt==n/3)break;
                }
            }
        }
        puts("");
    }
}