2618 - 最短路计数

给出一个N个顶点M条边的无向无权图,顶点编号1∼N。问从顶点1开始,到其他每个点的最短路有几条。

输入

第一行包含2个正整数N,M,为图的顶点数与边数。 接下来M行,每行2个正整数x,y,表示有一条由顶点x连向顶点 y的边,请注意可能有自环与重边。

输出

共N行,每行一个非负整数,第i行输出从顶点1到顶点i有多少条不同的最短路,由于答案有可能会很大,你只需要输出ans mod 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的最短路有4条,分别为2条 1→2→4→5 和2条 1→3→4→5(由于4→5 的边有 2条)。 对于20% 的数据,1≤N≤100; 对于60% 的数据,1≤N≤10^3; 对于100% 的数据,1≤N≤10^6,1≤M≤2×10^6。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题