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

我们定义：

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

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

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

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

输出共 N 行。

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

数据范围

• 对于 40\% 的数据，1 \le N, M \le 1000。

• 对于 100\% 的数据，1 \le N, M \le 10^5，图保证连通，无自环，无重边。

图论分层图最短路