[{"sectionTitle":"题目描述","type":"Text","text":" 给出一个 $N$ 个顶点 $M$ 条边的无向无权图，顶点编号为 $1\\sim N$。问从顶点 $1$ 开始，到其他每个点的最短路有几条。","subType":"markdown"},{"sectionTitle":"输入格式","type":"Text","text":"第一行包含 $2$ 个正整数 $N,M$，为图的顶点数与边数。\r\n\r\n接下来 $M$行，每行两个正整数 $x,y$，表示有一条顶点 $x$ 连向顶点 $y$ 的边，请注意可能有自环与重边。","subType":"markdown"},{"sectionTitle":"输出格式","type":"Text","text":"输出 $N$ 行，每行一个非负整数，第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 $\\bmod 100003$ 后的结果即可。如果无法到达顶点 $i$ 则输出 $0$。","subType":"markdown"},{"sectionTitle":"样例","type":"Sample","text":"$1$ 到 $5$ 的最短路有 $4$ 条，分别为 $2$ 条 $1 \\rightarrow 2 \\rightarrow 4 \\rightarrow 5$ 和 $2$ 条 $1 \\rightarrow 3 \\rightarrow 4 \\rightarrow5$（由于 $4 \\rightarrow 5$ 的边有 $2$ 条）。","subType":"markdown","payload":["5 7\n1 2\n1 3\n2 4\n3 4\n2 3\n4 5\n4 5","1\n1\n1\n2\n4"]},{"sectionTitle":"数据范围与提示","type":"Text","text":"对于 $20\\%$ 的数据，$N \\le 100$；\r\n\r\n对于 $60\\%$ 的数据，$N \\le 1000$；\r\n\r\n对于 $100\\%$ 的数据，$1 \\le N \\le 100000,0 \\le M \\le 200000$。","subType":"markdown"}]