2779: 「一本通 3.2 练习 3」最短路计数
Memory Limit：512 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：14
Solved：10
Description
给出一个 NNN 个顶点 MMM 条边的无向无权图，顶点编号为 1∼N1sim N1∼N。问从顶点 111 开始，到其他每个点的最短路有几条。
Input
第一行包含 222 个正整数 N,MN,MN,M，为图的顶点数与边数。
接下来 MMM行，每行两个正整数 x,yx,yx,y，表示有一条顶点 xxx 连向顶点 yyy 的边，请注意可能有自环与重边。
Output
输出 NNN 行，每行一个非负整数，第 iii 行输出从顶点 111 到顶点 iii 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 mod100003 后的结果即可。如果无法到达顶点 iii 则输出 000。
HINT
样例输入
5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5样例输出
1
1
1
2
4样例解释
111 到 555 的最短路有 444 条，分别为 222 条 1→2→4→51 ightarrow 2 ightarrow 4 ightarrow 51→2→4→5 和 222 条 1→3→4→51 ightarrow 3 ightarrow 4 ightarrow51→3→4→5（由于 4→54 ightarrow 54→5 的边有 222 条）。
对于 20%20\%20% 的数据，N≤100N le 100N≤100；
对于 60%60\%60% 的数据，N≤1000N le 1000N≤1000；
对于 100%100\%100% 的数据，1≤N≤100000,0≤M≤2000001 le N le 100000,0 le M le 2000001≤N≤100000,0≤M≤200000。