阅读须知：
思路参考y总的讲解，但是本代码采用直接枚举，更为客观，部分注释代码为debug使用

以第1位为开头，确定4个位置，可确定下一位的人选
举例：1的朋友为{2, 3, 4, 5}, 开始枚举 2 3 1 4这个顺序，
此时确定下一个一定是5，即2 3 1 4 5
依次类推，可以确定整个序列

但是需要一些特判，以{a, b, c, d}为dfs输入
假设下一位为e，即当前枚举序列为 a b c d e
当n>5时
a和d不能为朋友，b和e不能为朋友，d和e一定是朋友
当n==5时
5个元素中任意两个元素均为朋友

C++ 代码

#include <algorithm>
using namespace std;
#define DEBUG
#include <vector>
#include <cstring>
const int N=1e5+10;
int n;
vector<int> friends[N];

bool st[N];
vector<int> ans;

bool isfriend(int a, int b) //a和b是朋友
{
    for(auto it:friends[a]) if(b==it) return true;
    return false;
}

void init()
{

    read(n);
    for(int i=1; i<=n<<1; i++)
    {
        int a, b;
        read(a); read(b);
        friends[a].push_back(b);
        friends[b].push_back(a);
    }

    // for(int i=1; i<=n; i++) //输出朋友关系
    // {
    //     printf("%d:", i);
    //     for(int j=0; j<4; j++)
    //         printf("%d ", friends[i][j]);
    //     puts("");
    // }
    // puts("");
}

bool dfs(int fa2, int fa1, int u, int son1) // fa2 fa1 u son1 v
{
    if(st[u]) return false;
    st[u]=true;
    ans.push_back(u);
    if(ans.size()==n) return true;
    for(auto son2:friends[u])
    {
        if(son2==fa2 || son2==fa1 || son2==son1) continue; //去重
        if(n>5&&(isfriend(fa2, son1)||isfriend(fa1, son2))) continue;//特判关系 不能是朋友
        if(!isfriend(son1, son2)) continue; //特判关系 必须是朋友
        // printf("%d %d %d %d %d\n", fa2, fa1, u, son1, son2);
        if(dfs(fa1, u, son1, son2)) return true;
    }
    st[u]=false;
    ans.pop_back();
    return false;
}

void solve()
{
    init();
    for(int i=1; i<=n; i++)
    {
        auto fri=friends[i];
        if(fri.size()!=4) 
        {
            puts("-1"); 
            return;
        }
    }
    sort(friends[1].begin(), friends[1].end()); //全排列需要先排序
    do {
        if(n>5&&(isfriend(friends[1][0], friends[1][2])||isfriend(friends[1][1], friends[1][3]))) //特判关系 不能是朋友
            continue;
        ans.clear(); //init
        memset(st, 0, sizeof st);
        if(dfs(friends[1][0], friends[1][1], 1, friends[1][2])) break; //有解
    }while(next_permutation(friends[1].begin(), friends[1].end())); //全排列枚举

    if(ans.size())
    {
        for(int u:ans)
            quickwrite(u), putchar(' ');
        puts("");
    }      
    else puts("-1"); 
}

// #undef DEBUG
signed main()
{
    #ifdef DEBUG
        freopen("../in.txt", "r", stdin);
        freopen("../out.txt", "w", stdout);
    #endif
    #ifndef quickread
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #endif

    int T=1; //scanf("%d", &T);
    while(T--) 
    {
        solve();
    }
    return 0;
}