做法：链式前向星+bfs

前期一直MLE，一气之下数组开到2e6，居然没RE直接过了，不太能理解索性降到1e6居然还能过。

属实有点超出我的理解范围了，求大佬解答。

（一开始觉得MLE是类的原因所以都改成数组了）

import java.io.*;
import java.util.*;

public class Main{

//    static class Edge{
//        int to;
//        int next;
//        Edge(int to,int next){
//            this.to = to;
//            this.next = next;
//        }
//    }
    static int[] edgeto = new int[2000005];
    static int[] edgenext = new int[2000005];
//    static Edge[] edge = new Edge[2000005];
    static int[] head = new int[1000005];
    static int[] minnum = new int[1000005];
    static int[] sum = new int[1000005];
    static int cnt = 0;

    static void add(int u,int v){
        cnt++;
        edgeto[cnt] = v;
        edgenext[cnt] = head[u];
//        edge[cnt] = new Edge(v,head[u]);
        head[u] = cnt;
    }

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Read in = new Read(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        for(int i=1;i<=m;i++){
            int u = in.nextInt();
            int v = in.nextInt();
            add(u,v);
            add(v,u);
        }

        Queue<Integer> que = new LinkedList<>();
        que.add(1);
        sum[1]=1;
        while(!que.isEmpty()){
            int j = que.poll();
            int newfloor = minnum[j]+1;
            for(int i=head[j];i!=0;i=edgenext[i]){
                int to = edgeto[i];
                if(sum[to]==0){
                    sum[to]=sum[j];
                    minnum[to] = newfloor;
                    que.add(to);
                }
                else {
                    if(minnum[to]==newfloor){
                        sum[to] = (sum[to]+sum[j])%100003;
                    }
                }
            }
        }
        for(int i=1;i<=n;i++){
            System.out.println(sum[i]);
        }
    }
}












class Read {//自定义快读 Read

    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public Read(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public String nextLine() {
        String str = null;
        try {
            str = reader.readLine();
        } catch (IOException e) {
            // TODO 自动生成的 catch 块
            e.printStackTrace();
        }
        return str;
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public Double nextDouble() {
        return Double.parseDouble(next());
    }

//    public BigInteger nextBigInteger() {
//        return new BigInteger(next());
//    }
}