← 返回题目
题库练习 奇偶路径
← 上一题 下一题 →

A72010 | 奇偶路径

来源编程题
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

给定一个包含 N 个点和 M 条边的无向连通图，每条边的长度均为 1。

我们定义：

  • 奇数路径：从 1 号点出发，经过奇数条边到达目标点的路径。
  • 偶数路径：从 1 号点出发，经过偶数条边到达目标点的路径。

请你分别求出从 1 号点出发，到达每个点 i (1 \le i \le N) 的最短奇数路径长度和最短偶数路径长度。如果某种路径不存在，则输出 -1。

输入格式

第一行包含两个正整数 N 和 M，分别表示点数和边数。

接下来 M 行，每行包含两个正整数 u 和 v，表示点 u 和点 v 之间有一条无向边。

输出格式

输出共 N 行。

第 i 行包含两个整数，由空格隔开。第一个整数表示从 1 号点到点 i 的最短偶数路径长度，第二个整数表示最短奇数路径长度。

输入输出样例

输入 #1
3 2
1 2
2 3
输出 #1
0 -1
-1 1
2 -1
输入 #2
3 3
1 2
2 3
3 1
输出 #2
0 3
2 1
2 1
输入 #3
4 4
1 2
2 3
3 4
4 2
输出 #3
0 5
4 1
2 3
2 3
C++ 编辑器
输入
输出