先转化题目条件。
发现把 \(n\) 个点划分为 \(2\) 个点集，满足其中一个点集存在哈密顿路，另一个点集在补图中存在哈密顿路和原问题是等价的。
令直接存在哈密顿路的点集为 \(X\)，其路径端点分别为 \(S_X, T_X\)；补图中存在哈密顿路的点集为 \(Y\)，路径端点分别为 \(S_Y, T_Y\);
考虑 \(T_X\) 和 \(T_Y\) 是否有连边，有那就相当于是在 \(T_Y\) 这里进行了切换；否则就是在 \(T_X\) 这里进行了切换，所以和原问题等价。
考虑增量法求出 \(X, Y\)，当前加入了点 \(u\) 会有什么变化。
若 \(T_X, u\) 有连边，则 \(u\) 可以直接放进 \(X\) 里并作为新的 \(T_X\)。
同理，若 \(T_Y, u\) 没有连边，则 \(u\) 可以直接放进 \(Y\) 里并作为新的 \(T_y\)。
否则即 \(T_X, u\) 没有连边，\(T_Y, u\) 有连边时，考虑 \(T_X, T_Y\) 的连边关系。
若 \(T_X, T_Y\) 有连边，则 \(T_X \to T_Y \to u\) 都有连边，把 \(T_Y, u\) 放进 \(X\) 更新 \(T_X\) 即可。
同理若没有连边，则 \(T_Y\to T_X\to u\) 都没有连边，把 \(T_X, u\) 放进 \(Y\) 更新 \(T_Y\) 即可。
限制了路径的起点必须是 \(1\)。
考虑新加入的点 \(u\) 加入后肯定会是某一个集合的 \(T\)。
于是考虑倒序加点，哪部分 \(T = 1\) 就先走这部分，这部分从 \(T\) 走到 \(S\) 即可，因为 \(S, T\) 两者交换必然是不会影响的，毕竟是无向边。
用 map 存边，时间复杂度 \(O(n\log n)\)。
#include<bits/stdc++.h>
const int maxn = 3e5 + 10;
std::map<std::pair<int, int>, bool> E;
int a[maxn], la, b[maxn], lb;
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int x, y; scanf("%d%d", &x, &y);
E[{x, y}] = E[{y, x}] = 1;
}
for (int i = n; i >= 1; i--)
if (! la || E[{i, a[la]}]) a[++la] = i;
else if (! lb || ! E[{i, b[lb]}]) b[++lb] = i;
else if (E[{a[la], b[lb]}]) a[++la] = b[lb--], a[++la] = i;
else b[++lb] = a[la--], b[++lb] = i;
if (b[lb] == 1) std::swap(a, b), std::swap(la, lb);
for (int i = la; i; i--) printf("%d ", a[i]);
for (int i = lb; i; i--) printf("%d ", b[i]);
return 0;
}