#2242. 移动

移动

移动

题目描述

给定 个点 条边的无向图,点编号为 。 初始时, 号点处有一个持有物品的机器人。你可以进行以下操作:

  1. 令机器人将物品放置到相邻点;
  2. 令机器人从相邻点取走物品;
  3. 令未持有物品的机器人移动到未放置物品的相邻点。 操作 1, 2 需要耗费 个单位的时间,操作 3 不耗费时间。 求机器人移动到 且持有物品的最小时间。 输入格式 第一行: 接下来有 组测试数据,对于每组测试数据: 输出格式 对于每组测试数据: 一行 个整数,表示移动到 的最小时间。若无法到达输出 。 样例输入 4 4 4 1 2 2 3 3 4 4 1 5 5 1 2 2 3 3 4 4 5 5 1 5 6 1 2 3 2 1 3 3 5 5 4 3 4 9 12 1 2 2 3 3 1 4 5 5 6 6 4 7 8 8 9 9 7 3 6 6 9 9 3 样例输出 -1 2 -1 4 2 2 4 2 2 4 4 2 2 6 6 4 6 6 4 子任务 子任务编 分 特殊性质 号 值 无 无 无 保证边 存 在 所有点的度数不超过 无

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4
4 4
1 2
2 3
3 4
4 1
5 5
1 2
2 3
3 4
4 5
5 1
5 6
1 2
3 2
1 3
3 5
5 4
3 4
9 12
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7
3 6
6 9
9 3
-1 2 -1
4 2 2 4
2 2 4 4
2 2 6 6 4 6 6 4