← 返回题目
题库练习 路线数量
← 上一题 下一题 →

A71413 | 路线数量

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

题目描述

一张地图中标注了 N 个城市，城市编号为 1∼N ，城市之间通过双向的高速公路连接，假设走任意一条高速公路需要支付的费用都是相等的。

请问：从编号为 1 的城市出发，走到每个城市，如果期望支付最少的费用，请问有多少种不同的走法？

输入格式

第 1 行输入整数 N 和 M ，表示有 N 个城市， M 条双向的高速公路。

接下来 M 行，每行 2 个整数 x,y，代表从 x 到 y 之间有一条高速公路。

数据范围

1 \le N \le 100000,0 \le M \le 200000。

输出格式

输出 N 行，第 i 行代表，从 1 号城市到 i 号城市，支付最少路费的不同走法的数量，请输出结果数 \% 100003 的值。

如果无法走到 i 号点，请输出 0 。

输入输出样例

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