Source Code
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define p1 2*p
#define p2 p1+1
#define Mid (L+R)/2
#define ll long long
#define pb push_back
#define pf push_front
#define pi pair<int,int>
#define pii pair<int,pi>
#define deb(x) cout<<#x<<"="<<x<<endl
#define go ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
int n,m,mus=-1;
set <int> s[500500];
deque <int> ans,Mus,Ans;
vector <int> a[500500];
int vis1[500500];
bool vis[500500],used[500500];
vector <int> two[500500],one[500500];
vector <int> fuck[500500];
map <int,vector <int> > id[500500];
void f(set <int> now)
{
    ans.clear();
    Mus.clear();
    if(now.empty())
        return;
    mus=*now.begin();
    now.erase(mus);
    used[mus]=1;
    Mus.pb(mus);
    for(int x : one[mus])
        for(int i : id[mus][x])
        {
            if(vis[i]) continue;
            ans.pb(i);
            vis[i]=1;
        }
    int mod=0;
    for(int x : two[mus])
    {
        if(mod==0)
            for(int i : id[mus][x])
            {
                if(vis[i]) continue;
                Mus.pb(x);
                ans.pb(i);
                vis[i]=1;
            }
        else
            for(int i : id[mus][x])
            {
                if(vis[i]) continue;
                ans.pf(i);
                Mus.pf(x);
                vis[i]=1;
            }
        mod=1;
    }
    while(Mus.size())
    {
        mus=Mus.front();
        if(used[mus]) break;
        for(int x : one[mus])
            for(int i : id[mus][x])
            {
                if(vis[i]) continue;
                ans.pf(i);
                vis[i]=1;
            }
        mod=0;
        for(int x : two[mus])
        {
            if(mod==0)
                for(int i : id[mus][x])
                {
                    if(vis[i]) continue;
                    Mus.pf(x);
                    ans.pf(i);
                    vis[i]=1;
                }
            else
                for(int i : id[mus][x])
                {
                    if(vis[i]) continue;
                    ans.pf(i);
                    Mus.pf(x);
                    vis[i]=1;
                }
            mod=1;
        }
        Mus.pf(mus);
        used[mus]=1;
        now.erase(mus);
    }
    while(Mus.size())
    {
        mus=Mus.back();
        if(used[mus]) break;
        for(int x : one[mus])
            for(int i : id[mus][x])
            {
                if(vis[i]) continue;
                ans.pb(i);
                vis[i]=1;
            }
        mod=0;
        for(int x : two[mus])
        {
            if(mod==0)
                for(int i : id[mus][x])
                {
                    if(vis[i]) continue;
                    Mus.pb(x);
                    ans.pb(i);
                    vis[i]=1;
                }
            else
                for(int i : id[mus][x])
                {
                    if(vis[i]) continue;
                    ans.pb(i);
                    Mus.pb(x);
                    vis[i]=1;
                }
            mod=1;
        }
        Mus.pb(mus);
        used[mus]=1;
        now.erase(mus);
    }
    //deb("ans");
    for(int x : ans)
    {
        //   deb(x);
        Ans.pb(x);
    }
    f(now);
    return;
}
int main()
{
    go;
    cin>>n>>m;
    for(int i=0; i<n; i++)
    {
        int sz;
        cin>>sz;
        for(int j=0; j<sz; j++)
        {
            int A;
            cin>>A;
            mus=A;
            a[i].pb(A);
            vis1[A]=1;
        }
        if(sz==2)
        {
            id[a[i][0]][a[i][1]].pb(i);
            id[a[i][1]][a[i][0]].pb(i);
            s[a[i][0]].insert(a[i][1]);
            s[a[i][1]].insert(a[i][0]);
        }
        else
        {
            s[a[i][0]].insert(a[i][0]);
            id[a[i][0]][a[i][0]].pb(i);
          //  one[a[i][0]].pb(a[i][0]);
        }
    }
    for(int i=1; i<=m; i++)
        for(int x : s[i])
            if(s[x].size()>1)
                two[i].pb(x);
            else
                one[i].pb(x);
    set <int> s;
    for(int i=1; i<=m; i++)
        if(vis1[i])
            s.insert(i);
    f(s);
    //deb(Ans.size());
    if(Ans.size()==n)
    {
        int now=0;
        bool ok=1;
        for(int x : Ans)
        {
            fuck[a[x][0]].pb(now);
            if(a[x].size()>1)
                fuck[a[x][1]].pb(now++);
            else
                now++;
        }
        for(int i=1; i<=m; i++)
        {
            if(!vis1[i]) continue;
            for(int j=1; j<fuck[i].size(); j++)
            {
                int aa=fuck[i][j];
                int bb=fuck[i][j-1];
                ok&=aa==bb+1;
            }
        }
        if(ok)
            for(int x : Ans)
                cout<<x+1<<" ";
        else
            cout<<-1;
    }
    else
        cout<<-1;
    return 0;
}
Copy
Gym Grapeee
GNU G++17
55 ms
94.6 MB
Wrong Answer