from collections import deque
from collections import namedtuple as ntp
def main():
    #具名元组代替类
    edge = ntp('edge', ['to', 'next'])
    #节点数和边数
    n,m = map(int, input().split())
    edges, dis, head, nums = [0], [999999999 for i in range(n+1)], [0 for i in range(n+1)], [0 for i in range(n+1)]
    #输入边信息并链式前向星储存
    for i in range(1, m+1):
        u,v = map(int, input().split())
        edges.append(edge(v, head[u]))
        head[u] = i
    #初始化
    dis[1], q = 0, deque([1])
    nums[1] = 1
    '''
    
    SPFA
    
    '''
    while q:
        #q.pop()
        curnode = q.popleft()
        #当前节点的第一条边编号
        nxt = head[curnode]
        while 1:
            #当前节点的第下一条边
            curedge = edges[nxt]
            #如果边序号为0就跳出循环
            try:end = curedge.to
            except:break
            #发现更短距离时更新
            if 1 + dis[curnode] < dis[end]:
                dis[end] = 1 + dis[curnode]
                nums[end] = nums[curnode]
                if end not in q:q.append(end)
            #距离相同时相加
            elif 1 + dis[curnode] == dis[end]:
                nums[end] += nums[curnode]
                nums[end] = nums[end]%100003
            #下一条边
            nxt = curedge.next
    #打印
    for i in range(1, n+1):print(nums[i])
    return
main()

SPFA算法。能通过最后一个检查点但是通过不了第前四个。这个算法能通过基础版的最短路问题（除了超时）。