#include<iostream>
#include<limits>
#include<queue>
#include<vector>
#include<array>
constexpr int N=100003;
std::array<int,2000001>c,d;
int n,m,a,b,answer=0;std::array<std::vector<int>,2000001>mp;
void f(){
    d.fill(0x3f3f3f3f);
    std::queue<int>q;
    q.push(1);
    d.at(1)=0;
    c.at(1)=1;
    while(q.size()){
        for(int i{0};i<mp.at(q.front()).size();++i){
            int v=mp.at(q.front()).at(i);
            if(d.at(v)>d.at(q.front())+1){
                q.push(v),d.at(v)=d.at(q.front())+1;
                c.at(v)=c.at(q.front());
            }
            else if(d.at(v)==d.at(q.front())+1){
                c.at(v)=(c.at(v)%N+c.at(q.front())%N)%N;
            }
        }
        q.pop();
    }
}
int main(){
    std::cin>>n>>m;
    for(int i{1};i<=m;++i){
        std::cin>>a>>b;
        mp.at(a).push_back(b),mp.at(b).push_back(a);
    }
    f();
for(int i{1};i<=n;++i)
    std::cout<<c.at(i)<<'\n';
    return 0;
}