この問題を考えるうえで サイクル基底 (Cycle Bases) という概念が重要となります．まずはサイクル基底について説明します．この解説でグラフといった場合，単純連結無向グラフを指します．

---

サイクル基底について

グラフにはサイクルが多数存在します．いくつかのサイクルを辺の XOR（共通する辺は打ち消す）で足し合わせると別のサイクルが得られます（複数のサイクルになることもあります）．したがって，いくつかの基本となるサイクルを最小限列挙しておけば，他のサイクルはそれらの組合せで再現することができそうです．この「最小限のサイクルの集合」がサイクル基底です．

サイクル空間，サイクル基底の定義

グラフ \(G=(V,E)\) を考えます．各頂点の次数がすべて偶数であるような \(G\) の部分グラフ全体の集まり \(\mathcal{C}(G)\) を サイクル空間 と呼びます．

\(\mathcal{C}(G)\) の要素同士には，XOR 演算（辺の対称差）が自然に定義できます．すなわち，\(H_1,H_2\in \mathcal{C}(G)\) に対して，\(H_1\oplus H_2\) を「\(H_1\) または \(H_2\) のいずれか一方にのみ含まれる辺全体を辺集合とする \(G\) の部分グラフ」とすると，\(H_1\oplus H_2\in \mathcal{C}(G)\) です．（\(\mathcal{C}(G)\) は \(\oplus\) に関して群です．単位元は空グラフ，逆元は自分自身．）

\(\mathcal{C}(G)\) の中で，次を満たす単純サイクルの集合 \(\mathcal{B}\) を サイクル基底 と呼びます．（これは，\(\mathbb{F}_2\) のベクトル空間における XOR 基底と似たようなものです．）

1. 任意の \(C\in \mathcal{C}(G)\) は，いくつかの \(\mathcal{B}\) に含まれるサイクルの XOR（\(\oplus\)）で表すことで得られる．
2. \(\mathcal{B}\) のどのサイクルも，\(\mathcal{B}\) のほかのサイクルの XOR で表すことができない．

---

ここから，いくつかの事実を述べていきます．

事実 1.

サイクル基底 \(\mathcal{B}\) は以下の手順で得られることが知られています．

1. \(G\) の全域木 \(T\) を任意に \(1\) つとる．
2. \(T\) に含まれない \(G\) の辺 \(e=(u,v)\) について，\(T\) 上の \(u\) から \(v\) への単純パスを \(P\) として \(C_e=P\cup\lbrace e\rbrace\) を \(\mathcal{B}\) に 追加する．

事実 2.

サイクル基底のサイズは \(|E|-|V|+1\) です．これは上のサイクル基底を得る手順からわかります．

事実 3.

\(G\) に含まれる単純サイクルはすべて \(\mathcal{C}(G)\) に含まれ，その個数は \(2^{|E|-|V|+1}\) 以下です．

事実 4.

頂点 \(s,t\ (s,t\in V)\) を結ぶ単純パスの個数は \(2^{|E|-|V|+1}\) 以下です．

（証明）
\(s\text{-}t\) 単純パスを任意に一つ固定し \(P_0\) とします．ある \(s\text{-}t\) 単純パス \(P\) に対して \(P\oplus P_0\) を考えると，これは \(\mathcal{C}(G)\) の要素になります．異なる \(s\text{-}t\) 単純パス \(P_1, P_2\) に対して \(P_0\oplus P_1\neq P_0\oplus P_2\) であるため，\(s\text{-}t\) 単純パスの個数は \(|\mathcal{C}(G)|= 2^{|E|-|V|+1}\) 以下です．

---

本問題の解法

事実 4. をうまく利用した解法を紹介します．\(K\) をサイクル基底のサイズ \(M-N+1\) とします．

計算量を一旦無視すると，次のコードによって答えを計算することができます（G は隣接頂点リスト）．

visited = [0] * (N + 1)
ans = [0] * N

def dfs(v, L):
    visited[v] = 1
    if v == N:
        ans[L] += 1
    for u in G[v]:
        if visited[u] == 0:
            dfs(u, L + 1)
    visited[v] = 0
dfs(1, 0)

このコードにおいて，dfs 関数が呼び出される回数は \(N2^K\) 回以下です．

（証明：dfs が呼び出される回数は頂点 \(1\) からの単純パスの個数と同じです．\(1\text{-}v\) 単純パスの個数は事実 4. より高々 \(2^K\) であるため，dfs が呼び出される回数は \(N2^K\) 以下です．）

このままだとグラフのサイズが大きいため間に合いませんが，グラフを縮約することでサイズを小さくすることができます．

まず，次数が \(1\) であるような頂点 \(v\ (v\neq 1,N)\) はどの \(1 \text{-}N\) 単純パスにも含まれないので削除してよいです．次数が \(1\) の頂点が \(1,N\) 以外にない状態のグラフにおいて，頂点集合を \(S=\lbrace 1,N\rbrace\cup \lbrace v\mid \mathrm{deg}[v]\geq 3\rbrace\) とする重み付きグラフ \(H\) を作ります．\(S\) に含まれない頂点はすべて次数が \(2\) なので，単純パスの縮約が行えます．すなわち，\(u,v\in S\) に対し，途中に \(S\) の頂点を含まない \(u\text{-}v\) 単純パスが存在するたびに，その単純パスを重み付き辺に置き換えて \(H\) に追加します（重みは単純パスの長さ）．\(H\) の頂点数は高々 \(2K+2\)，辺数は高々 \(3K+1\) であるため，この \(H\) において上と同様の dfs をすることで，本問題を \(O(N+K2^K)\) 時間で解くことができます．

---

別の解法として，サイクル基底を利用して \(\mathcal{C}(G)\) の要素をすべて列挙できるようにておき，適当な \(1\text{-}N\) 単純パス \(P_0\) を固定したうえで，各 \(C\in \mathcal{C}(G)\) に対して \(P_0\oplus C\) が単純パスになるかを確認する方法もあります．

この解法も同様にグラフのサイズを小さくする処理が必要です．縮約後のグラフにおいて，辺の本数は高々 \(3K+1\leq 64\) であるため，\(P_0\) や \(\mathcal{C}(G)\) の各サイクルがどの辺を含むかどうかは 64bit 整数で表現可能です．各 \(C\in \mathcal{C}(G)\) に対して，\(C\) がどのような 64bit 整数で表現できるかや \(P_0\oplus C\) が \(1\text{-}N\) 単純パスであるかどうかをそれぞれ \(O(K)\) で計算できるようにすれば，同じ時間計算量 \(O(N+K2^K)\) を達成できます．

---

実装例（dfs 方針）

N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    u, v = map(lambda x: int(x) - 1, input().split())
    G[u].append((v, i))
    G[v].append((u, i))

deg = [len(g) for g in G]
T = [1] * N
st = [v for v in range(N) if v not in (0, N - 1) and deg[v] == 1]
while st:
    v = st.pop()
    if v == 0 or v == N - 1:
        continue
    T[v] = 0
    for u, _ in G[v]:
        deg[u] -= 1
        if deg[u] == 1:
            st.append(u)

S = [0] * N
for v in range(N):
    if v == 0 or v == N - 1 or (T[v] == 1 and deg[v] >= 3):
        S[v] = 1
H = [[] for _ in range(N)]
used = [0] * M

for s in range(N):
    if S[s] == 0:
        continue
    for v, e in G[s]:
        if not T[v] or used[e]:
            continue
        used[e] = 1
        l = 1
        par, cur = s, v
        while T[cur] == 1 and S[cur] == 0 and deg[cur] == 2:
            g = [x for x in G[cur] if T[x[0]]]
            nxt, e2 = g[0] if g[0][0] != par else g[1]
            used[e2] = 1
            l += 1
            par, cur = cur, nxt
        H[s].append((cur, l))
        H[cur].append((s, l))

ans = [0] * N
visited = [0] * N


def dfs(v, d):
    if v == N - 1:
        ans[d] += 1
        return
    visited[v] = 1
    for u, l in H[v]:
        if visited[u] == 0:
            dfs(u, d + l)
    visited[v] = 0


dfs(0, 0)
print(*ans[1:])