logo AlgoBeat OnlineJudge
登录 注册

#215921. 【MX-X26-T5】「Cfz Round 7」anybody can finds love (expect you)

内存限制:512 MiB 时间限制:1500 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

给定一张包含 个点和 条边的可能有重边的无向连通图

定义一个由边构成的序列 是「鱼鱼」的,当且仅当:

  1. 可重集 与边集 相同;
  2. 对于所有 的终点与 的起点相同;
  3. 对于所有 的起点与 的终点不同;
  4. 的起点与 的终点相同。

即序列 形成了一条欧拉回路,且回路中不存在 的形状。

你需要构造一个「鱼鱼」的序列,或报告不存在「鱼鱼」的序列。

为了方便,当「鱼鱼」的序列存在时,你只需要按照回路的顺序给出经过的点即可。

输入格式

本题有多组测试数据。

输入的第一行包含两个整数 ,分别表示该测试点所属的子任务编号和测试数据组数。样例满足

接下来依次输入每组测试数据。对于每组测试数据:

  • 第一行包含两个整数
  • 接下来 行,每行包含两个整数 ,表示图中存在一条连接结点 和结点 的边。

输出格式

对于每组测试数据:

  • 如果无解,输出一行,包含一个整数
  • 否则,输出一行,包含 个整数,表示按照回路的顺序依次经过的点。

样例

样例输入 1

0 2
4 6
1 2
3 1
2 3
2 4
3 4
3 2
2 2
1 2
1 2

样例输出 1

2 3 1 2 3 4 2
-1

数据范围与提示

样例 1 解释

对于第 组测试数据, 同样为「鱼鱼」的序列,但 不为「鱼鱼」的序列。

对于第 组测试数据,容易证明不存在「鱼鱼」的序列。

数据范围

对于所有测试数据,均有:

  • 对于所有 ,均有
  • 给出的无向图连通。

本题采用捆绑测试。

  • Subtask 1(15 points):
  • Subtask 2(18 points):
  • Subtask 3(15 points):对于所有 ,保证连接结点 与结点 的边不超过 条。
  • Subtask 4(24 ponits):对于所有 ,保证连接结点 与结点 的边不超过 条。
  • Subtask 5(28 points):无特殊限制。