首先转化一下题意。题目重点是无序二元组，不难由此想到图论建图。下面直接给出转化后的题意：给定 \(n\) 个点，\(2n-3\) 条边的无向简单图（\(n\ge 4\)），求出图中两个长度相等的不同简单环（这里不同定义为边集不完全相等），或报告无解。
直接出图论版本多好，现在这个题面看上去像硬编出来的，很不自然。
先考虑图连通的情况。注意到题目给的边数是一个奇奇怪怪的 \(2n-3\)，可以猜想一定有解。
考虑有什么方式在一个图上描述一个环。一个最方便的方式是找出一棵生成树，那么每条非树边加上两个端点在树上的路径就构成一个环。在这题中，共有 \(n-2\) 条非树边，得到 \(n-2\) 个不同的环。而且，这些环长一定不小于 \(3\)，不大于生成树直径的点数（设为 \(D\)），故在 \(D\le n-1\) 时，由抽屉原理，这些环中一定有两个长度相等的。
而这个图中也一定可以找到 \(D\le n-1\) 的生成树。由 \(|E|=2n-3\) 且 \(n\ge 4\) 知一定有一个度数不小于 \(3\) 的点 \(x\)，考虑从 \(x\) 开始的 bfs 树，在树上 \(x\) 的度数也不小于 \(3\)，所以这棵生成树不是链，必然有 \(D\le n-1\)。
对于图不连通的情况，不难发现一定有一个连通块 \((V,E)\) 满足 \(|E|>2|V|-3\)（而由简单图的性质也能说明此时 \(|V|\ge 4\)），此时甚至随便找一棵生成树都可行。
上述做法瓶颈在于求树上两点距离，用倍增/树剖求 LCA 可以做到 \(\mathcal O(n\log n)\)，用线性 LCA 算法可以做到 \(\mathcal O(n)\)。
不过求 LCA 的算法都太复杂了，事实上这个题还有更简洁的线性做法。
bfs 树性质不够好，考虑选一个性质更优美的生成树。任选起点求出 dfs 树，在 dfs 树上，所有非树边一定是祖先后代边，这样就不需要求 lca 了，直接通过深度差就能求出环长。
但 dfs 树不能保证 \(D\le n-1\)。假设任选了一个起点求出的 dfs 树是一条链，且 \(n-2\) 条非树边对应的环长恰好是 \(3\sim n\)，此时有两种可行的解决方法。
第一种是沿用上面的思路。还是先找到一个度数不小于 \(3\) 的点开始 dfs，设得到的 dfs 树（根据假设这是一条链）上的点依次为 \(p_1,p_2,\dots,p_n\)。由于此时非树边对应环长为 \(3\sim n\)，边 \((p_1,p_n)\) 一定存在，同时一定存在点 \(x\notin\{p_2,p_n\}\) 满足边 \((p_1,x)\) 存在。那么从 \((p_1,x)\) 这条边开始 dfs （就是将这条边换到 \(p_1\) 相邻的第一条边），得到另一棵 dfs 树。考虑这棵 dfs 树上非树边对应的 \(n-2\) 个环，如果环长重复则找到答案；否则同上一定找到了一个长为 \(n\) 的环，且由于 \((p_1,x)\) 在这个环上，所以这个环和前一个长为 \(n\) 的环不同，故也找到答案。
第二种是考虑一些包含更多非树边的环，具体地是包含两条非树边的环。由于包含一条非树边的环长已经覆盖了 \([3,n]\)，所以只要任意找到一个包含两条非树边的简单环即可。不妨设 dfs 树（链）上的点依次为 \(1,2,\dots,n\)。下面将说明：一定存在 \(i\in [1,n]\)，使得要么存在 \(i+1<j<k\) 满足边 \((i,j),(i,k)\in E\)，要么存在 \(k<j<i-1\) 满足边 \((i,j),(i,k)\in E\)。
考虑反证法，假设结论不成立。对于点 \(1\)，由结论不成立，它只与 \(3\sim n\) 中至多一个点相连。由于存在一条非树边对应环长为 \(n\)，所以 \((1,n)\in E\)。类似地，可以说明 \((2,n),(3,n),\dots,(n-2,n)\in E\)，在这 \(n-2\) 条边中任取两条即可导出矛盾。
而对于 \(i+1<j<k\) 且 \((i,j),(i,k)\in E\)，可以找到环 \(i,j,j+1,j+2,\dots,k\) 包含两条非树边。\(k<j<i-1\) 同理。根据上面的证明过程不难找出一组这样的 \((i,j,k)\)。
总复杂度 \(\mathcal O(n)\)。
需要 LCA 的做法没写，只能提供后面的两种 dfs 树做法的代码实现。
第一种 dfs 树做法：
#include <bits/stdc++.h>
typedef std::pair<int, int> pii;
#define fi first
#define se second
#define MP std::make_pairint read()
{int s = 0; int f = 1, c = getchar();for (; !isdigit(c); c = getchar()) f ^= (c == '-');for (; isdigit(c); c = getchar()) s = s * 10 + (c ^ 48);return f ? s : -s;
}
template<typename T>
void write(T x, char end = '\n')
{if (x < 0) x = -x, putchar('-');static int d[100], cur = 0;do { d[++cur] = x % 10; } while (x /= 10);while (cur) putchar(48 ^ d[cur--]);putchar(end);
}
const int MAXN = 100005;
int n, V, E;
std::vector<int> e[MAXN];
int id[MAXN], fa[MAXN], dep[MAXN];
bool vis[MAXN];
void count(int x, int fat)
{id[++V] = x, E += e[x].size();fa[x] = fat, dep[x] = dep[fat] + 1;for (int y : e[x]) if (!dep[y]) count(y, x);
}
int iidd[MAXN], VV;
void dfs(int x, int fat)
{iidd[++VV] = x;fa[x] = fat, dep[x] = dep[fat] + 1;for (int y : e[x]) if (!dep[y]) dfs(y, x);
}
void solve(int rt)
{static pii loop[MAXN];for (int i = 3; i <= n; i++) loop[i] = MP(0, 0);auto printPath = [](int x, int y, char end){for (; x != y; x = fa[x]) write(x, ' ');write(x, end);};for (int i = 1; i <= V; i++){int x = id[i];for (int y : e[x]) if (dep[y] < dep[x] - 1){int len = dep[x] - dep[y] + 1;if (loop[len].fi){write(len);printPath(loop[len].fi, loop[len].se, '\n');printPath(x, y, '\n');return ;}loop[len] = MP(x, y);}}for (int j = 0; ; j++)if (e[id[1]][j] != id[2] && e[id[1]][j] != id[V]){ std::swap(e[id[1]][j], e[id[1]][0]); break; }for (int i = 1; i <= V; i++) dep[id[i]] = fa[id[i]] = 0;VV = 0, dfs(id[1], 0);for (int i = 3; i <= n; i++) loop[i] = MP(0, 0);for (int i = 1; i <= V; i++){int x = id[i];for (int y : e[x]) if (dep[y] < dep[x] - 1){int len = dep[x] - dep[y] + 1;if (loop[len].fi){write(len);printPath(loop[len].fi, loop[len].se, '\n');printPath(x, y, '\n');return ;}loop[len] = MP(x, y);}}write(V);for (int i = 1; i <= V; i++) write(id[i], " \n"[i == V]);for (int i = 1; i <= V; i++) write(iidd[i], " \n"[i == V]);
}
int main()
{n = read();for (int i = 1; i <= n * 2 - 3; i++){int u = read(), v = read();e[u].push_back(v), e[v].push_back(u);}for (int i = 1; i <= n; i++)if (!vis[i] && e[i].size() >= 3) {V = E = 0, count(i, 0), E >>= 1;if (V >= 4 && E >= V * 2 - 3)return solve(i), 0;}return 0;
}
第二种 dfs 树做法：
#include <bits/stdc++.h>
typedef std::pair<int, int> pii;
#define fi first
#define se second
#define MP std::make_pairint read()
{int s = 0; int f = 1, c = getchar();for (; !isdigit(c); c = getchar()) f ^= (c == '-');for (; isdigit(c); c = getchar()) s = s * 10 + (c ^ 48);return f ? s : -s;
}
template<typename T>
void write(T x, char end = '\n')
{if (x < 0) x = -x, putchar('-');static int d[100], cur = 0;do { d[++cur] = x % 10; } while (x /= 10);while (cur) putchar(48 ^ d[cur--]);putchar(end);
}
const int MAXN = 100005;
int n, V, E;
std::vector<int> e[MAXN];
int id[MAXN], fa[MAXN], dep[MAXN];
bool vis[MAXN];
void count(int x, int fat)
{id[++V] = x, E += e[x].size();fa[x] = fat, dep[x] = dep[fat] + 1;for (int y : e[x]) if (!dep[y]) count(y, x);
}
void solve(int rt)
{static pii loop[MAXN];for (int i = 3; i <= n; i++) loop[i] = MP(0, 0);auto printPath = [](int x, int y, char end){for (; x != y; x = fa[x]) write(x, ' ');write(x, end);};for (int i = 1; i <= V; i++){int x = id[i];for (int y : e[x]) if (dep[y] < dep[x] - 1){int len = dep[x] - dep[y] + 1;if (loop[len].fi){write(len);printPath(loop[len].fi, loop[len].se, '\n');printPath(x, y, '\n');return ;}loop[len] = MP(x, y);}}for (int i = 1; ; i++){int x = 0, y, z;if (e[id[i]].size() >= 3) x = id[i];else if (e[id[V + 1 - i]].size() >= 3) x = id[V + 1 - i];if (!x) continue;y = e[x][0], z = e[x][1];if (std::abs(dep[x] - dep[y]) == 1) y = e[x][2];if (std::abs(dep[x] - dep[z]) == 1) z = e[x][2];if (dep[y] < dep[z]) std::swap(y, z);int len = dep[y] - dep[z] + 2;write(len);printPath(y, z, ' '), write(x);printPath(loop[len].fi, loop[len].se, '\n');break;}
}
int main()
{n = read();for (int i = 1; i <= n * 2 - 3; i++){int u = read(), v = read();e[u].push_back(v), e[v].push_back(u);}for (int i = 1; i <= n; i++)if (!vis[i]) {V = E = 0, count(i, 0), E >>= 1;if (V >= 4 && E >= V * 2 - 3)return solve(i), 0;}return 0;
}