Source Code
#include<bits/stdc++.h>
#define ll long long 

using namespace std;
ll MOD = 1e9 + 7 ;
ll bigMod(ll x,ll y){
    if (y == 0)return 1;
    if (y == 1)return x;
    ll res = bigMod(x , y / 2LL);
    res *= res;
    res %= MOD;
    if (y % 2){
        res *= x;
        res %= MOD;
    }
    return res;
}
ll fac[1000005];
ll choose(ll x,ll y){
    if (x == y)return 1;
    if (y > x)return 0;
    if (y == 0)return 1;
    ll up = fac[x];
    ll down = fac[y] * fac[x-y];
    down %= MOD;
    ll ret = up * bigMod(down , MOD - 2);
    ret %= MOD;
    return ret;
}

ll n , m;
map<pair<int,int> , vector<int> > ma;
vector<int> v[500005];
int last[500005];
vector<int> inside[500005];
bool vis[500005];
vector<int> ans;
map<pair<int,int> , bool> ma2;
bool bla;
void dfs(int s,int pa){
    if (vis[s]){
        bla = 1;
        return;
    }
    vis[s] = 1;
    for (int x : inside[s]){
        ans.push_back(x);
    }
    for (int u : v[s]){
        if (u != pa){
            for (int x : ma[{s,u}])ans.push_back(x);
            if (inside[u].size() > 0 || v[u].size() > 1)
                dfs(u , s);
            else vis[u] = 1;
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i=1;i<=n;i++){
        int t;
        cin >> t;
        if (t == 1){
            int x;
            cin >> x;
            inside[x].push_back(i);
        }
        else {
            int x,y;
            cin >> x >> y;
            ma[{x,y}].push_back(i);
            ma[{y,x}].push_back(i);
            if (ma2.find({x,y}) == ma2.end())
                {v[x].push_back(y);ma2[{x,y}] = 1;}
            if (ma2.find({y,x}) == ma2.end())
                {v[y].push_back(x);ma2[{y,x}] = 1;}
        }
    }
    int cnt = 0;
    set<int> se , se2;
    for (int i=1;i<=m;i++){
        // cout << i << "      " << v[i].size() << endl;
        // if (v[i].size() > 2){
        //     cout << -1 << endl;
        //     return 0;
        // }
        if (v[i].size() == 0 && inside[i].size() != 0){
            se2.insert(i);
        }
        if (v[i].size() == 1){
            se.insert(i);
        }
    }
    for (int x : se2){
        for (int y : inside[x])ans.push_back(y);
    }
    for (auto x : se){
        if (!vis[x]){
            cout << x << endl;
            dfs(x , -1);
        }
    }
    for (int i=1;i<=m;i++){
        if (v[i].size() > 0 && !vis[i]){
            dfs(i , -1);
        }
    }
    if (bla){
        cout << -1 << endl;
        return 0;
    }
    for (int x : ans)cout << x << " ";
    cout << endl;
    return 0;
}
Copy
Gym Khaled97ha
GNU G++17
13 ms
23.8 MB
Wrong Answer