本题没有可用的提交语言。

问题描述

考虑一个无向图$G = \langle V,E \rangle$。用$N(v)$表示与顶点$v$相连的顶点集合（即$v$的邻居集合）。顶点$v$的度数$deg\ v$定义为与其相连的顶点数量。

我们称图$G$为奇异图，如果它满足以下条件：

1. 连通性：图$G$是连通的。
2. 度数限制：
   • 对于每个顶点$v$，$deg\ v \geq 2$。
   • 如果$deg\ v = 2$，则$v$的两个邻居之间没有边相连。
   • 如果$deg\ v > 2$，则存在一个邻居$u \in N(v)$满足：
     • $deg\ u = 2$；
     • 对于任意两个不同的顶点$w_1,w_2 \in N(v) \setminus \{u\}$，$(w_1,w_2) \in E$。

给定一个奇异图$G$，找出其中的哈密顿回路（即经过每个顶点恰好一次的回路）。若不存在，则输出$-1$。

输入格式

• 第一行：两个整数$N$和$M$，分别表示顶点数和边数（$3 \leq N \leq 10\,000$，$M \leq 100\,000$）。
• 接下来$2M$个整数：每对整数表示一条边的两个顶点（顶点编号从$1$到$N$）。保证每条边在输入中只出现一次，且无自环。

输出格式

• 若无哈密顿回路，输出$-1$。
• 否则，输出$N$个整数，表示哈密顿回路的顶点序列（首尾相连）。若有多解，输出任意一个。

示例输入与输出

输入示例：

4 4
1 2 2 3 3 4 4 1

输出示例：

1 2 3 4

数据来源

2002年东北欧，北部子区域