A72010. 奇偶路径
编程题
基础
知识点
题目描述
给定一个包含 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
说明/提示
数据范围
对于 40\% 的数据，1 \le N, M \le 1000。
对于 100\% 的数据，1 \le N, M \le 10^5，图保证连通，无自环，无重边。