1466F - Euclid's nightmare - CodeForces Solution

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define B break
#define C continue
#define R return
#define mid ((l+r)/2)
#define left (2*idx)
#define right (2*idx+1)

using namespace std;

const ll Mod=1e9+7 , N = 500500 , inf=1e18;
ll n , m , k , q , x , y , z , a[N] , vis[N] , special[N] , done[N] , ans[N] , sum=0 , mn=inf , mx=0 ;

ll par[N],sz[N];
ll get_par(ll x){
    if(x==par[x])return x;
    R par[x]=get_par(par[x]);
}
void mrg(ll x , ll y){
    x=get_par(x),y=get_par(y);
    if(x==y)R;
    if(sz[x]<sz[y])swap(x,y);
    sz[x]+=sz[y] , par[y]=x , special[x] |= special[y];
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m ;
    for(int i=1 ; i<=m ; i++){
        sz[i]=1;
        par[i]=i;
        special[i]=0;
    }
    vector<pair<ll,pair<ll,ll>>>v;
    for(int i=1 ; i<=n ; i++){
        cin >> k ;
        if(k==1){
            cin >> x;
            ll parent = get_par(x);
            if(!special[parent]){
                ans[i]=1;
            }
            special[parent]=1;
        }
        else{
            cin >> x >> y ;
            ll parx = get_par(x);
            ll pary = get_par(y);
            if(parx==pary)C;
            if(!special[parx] || !special[pary]){
                ans[i]=1;
            }
            mrg(x,y);
        }
    }
    ll res=0,res2=1;
    for(int i=1 ; i<=n ; i++){
        if(ans[i])res++;
    }
    for(int i=1 ; i<=res ; i++){
        res2 = (res2+res2)%Mod;
    }
    cout << res2 << " " << res << '\n';
    for(int i=1 ; i<=n ; i++){
        if(ans[i])cout << i << " ";
    }
    cout << endl ;

    return 0;
}