一张地图中标注了 N 个城市，城市编号为 1∼N ，城市之间通过双向的高速公路连接，假设走任意一条高速公路需要支付的费用都是相等的。
请问：从编号为 1 的城市出发，走到每个城市，如果期望支付最少的费用，请问有多少种不同的走法？
第1行输入整数N和M，表示有N个城市，M条双向的高速公路。
接下来M行，每行2个整数x,y，代表从x到y之间有一条高速公路。
1≤N≤100000,0≤M≤200000。
输出N行，第i行代表，从1号城市到i号城市，支付最少路费的不同走法的数量，请输出结果数 % 100003的值。
如果无法走到 i 号点，请输出 0。
5 7 1 2 1 3 2 4 3 4 2 3 4 5 4 5
1 1 1 2 4
样例解释
从城市 1 走到城市 5 ，最少需要经过 3 条高速公路，这样的不同走法有 4 种，分别是：1→2→4→5（2种走法，因为4→5有2条路） 和 1→3→4→5（2种走法，因为4→5有2条路）。