#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e6 + 10;
vector<int> G[N], DAG[2 * N];
 
bool v[2 * N];
int d[N], in[2 * N], f[2 * N], path[2 * N], ans[2 * N];
queue<int> Q;
 
int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;
	n *= 2;     // 别忘了 
	memset(d, 0, sizeof(d));
	for (int i = 1; i <= m; i ++) {
		int x, y;
		cin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
		d[x] ++; d[y] ++;
	}
	
	memset(v, 0, sizeof(v));
	memset(in, 0, sizeof(in));
	
	for (int i = 1; i <= n; i ++) if (d[i] == 1) {
		Q.push(i);   // 一度点 
	}
	
	while (!Q.empty()) {
		int x = Q.front(); Q.pop();
		if (v[x]) {
			continue;
		}
		v[x] = 1;   // 表示这个点已经被选入最终红绿图了 
		
		for (int y : G[x]) if (!v[y]) {
			DAG[x].push_back(y + n);
			DAG[y].push_back(x + n);
			in[y + n] ++;   // in 表示这个点的入度 
			in[x + n] ++;
			v[y] = 1;    // 只标记不入队
			// 因为和 y 相连的绿边我们会直接在这个循坏处理
			// 避免 y 入队又找一条绿边的情况 
			
			for (int z : G[y]) if (!v[z]) {
				DAG[y + n].push_back(z);
				DAG[z + n].push_back(y);
				in[z] ++;
				in[y] ++;
				d[z] --;
				if (d[z] == 1) {  // 一度点入队 
					Q.push(z);
				}
			}
		}
	}
	
	memset(v, 0, sizeof(v));
	memset(f, 0, sizeof(f));
	memset(path, 0, sizeof(path));
	
	for (int i = 1; i <= n; i ++) if (in[i] == 0) {
		Q.push(i);
		v[i] = 1;
	}
	
	while (!Q.empty()) {
		int x = Q.front(); Q.pop();
		for (int y : DAG[x]) {
			if (f[y] < f[x] + 1) {    // 尽量多叠层 
				f[y] = f[x] + 1;
				path[y] = x;
			}
			in[y] --;
			if (in[y] == 0) {
				Q.push(y);
			}
		}
	}
	
	int mx = 0, p = 0;
	for (int i = 1; i <= 2 * n; i ++) {
		if (mx < f[i]) {
			mx = f[i];    // 找到叠层叠得最多的 
			p = i;
		}
	}
	
	int len = 0;
	while (p != 0) {
		len ++;
		ans[len] = p;
		p = path[p];
	}
	
	cout << len << "\n";
	for (int i = 1; i <= len; i ++) {
		if (ans[i] > n) {
			ans[i] -= n;
		}
		cout << ans[i] << " ";
	}
	cout << "\n";
	
	return 0;
} 

题解：P14779 宴会

设 $P_i$ 为 $i$ 的匹配点。

首先第一步肯定是先把原匹配给还原回来，由于保证构造方式唯一，所以一定总能找到一个一度点。

证明：如果此时图中没有一个一度点，我们将匹配还原后一定能找到图中的一个形如以下两种形式之一的环：

1. $i\rightarrow P_i\rightarrow j \rightarrow P_j ... k\rightarrow P_k\rightarrow i$

2. $i\rightarrow P_i\rightarrow j \rightarrow P_j ... k\rightarrow P_k\rightarrow P_i$ 其中 $i$ 为环外点。

那么形式 1 可以通过转一圈的方式使构造不唯一，形式 2 可以通过转一圈后将 $P_i=P_k$ 使构造不唯一，所以总能找到一个一度点。

此时我们不断删去这个一度点和与其相连的那个点并把它们匹配起来，这个过程可以用拓扑实现，复杂度 $O(n)$。

然后重点来了，由于走到每个点时会优先走到匹配点，所以访问序列必然是形如：$i\rightarrow P_i\rightarrow j \rightarrow P_j \rightarrow k$......

这个应该很好理解，就不解释了。那么我们考虑对原图进行一个转化，即将 $P_i$ 的所有出边连到 $i$ 上，那么我们每次走到点 $i$ 再走到另一个点 $u$ 就相当于走了点 $i$ 又到 $P_i$ 再到 $u$。

那么最大化路径长度就相当于找到图的最长链。

那么如果图中有环怎么办？不会的。如果我们走出了一个环，那么这个环一定长度 $\ge 4$ 我们仍可以通过转一圈来使构造方案不唯一，因此图是个 DAG。

那么 DAG 上的最长链就很好求了，依然通过拓扑序转移即可，转移时记录一下前驱就能输出方案了。

时间复杂度 $O(n)$。

::::success[Code]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
const int N=1e6+5;
vector<int>g[N],e[N];
int n,ans,deg[N],p[N],tuo[N],m,f[N],pre[N];
void write(int x){
	if(pre[x])write(pre[x]);
	printf("%d %d ",p[x],x);
}
int main(){
	scanf("%d%d",&n,&m);
	n<<=1;
	for(int i=1,u,v;i<=m;++i){
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
		deg[u]++,deg[v]++;
	}
	queue<int>q;
	for(int i=1;i<=n;++i)
		if(deg[i]==1)q.push(i);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		if(p[u])continue;
		for(auto v : g[u])
			if(!p[v]){
				p[u]=v;
				p[v]=u;
				for(auto to : g[v])
					if(!p[to]&&--deg[to]==1)q.push(to);
				break;
			}
	}
	memset(deg,0,sizeof(deg));
	for(int i=1;i<=n;++i)
		for(auto v : g[p[i]])
			if(v!=i)e[i].push_back(v),++deg[v];
	for(int i=1;i<=n;++i)
		if(!deg[i])q.push(i);
	int cnt(0);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		tuo[++cnt]=u;
		for(auto v : e[u])
			if(!--deg[v])q.push(v);
	}
	for(int i=n;i;--i){
		int u=tuo[i];
		f[u]=2;
		for(auto v : e[u])
			if(f[v]+2>f[u]){
				f[u]=f[v]+2;
				pre[u]=v;
			}
		ans=max(ans,f[u]);
	}
	printf("%d\n",ans);
	for(int i=1;i<=n;++i)
		if(f[i]==ans){
			write(i);
			return 0;
		}
	return 0;
}

::::