An important concept to solve this problem is cycle bases. We will explain this first. In this editorial, a graph refers to a simple undirected graph.

---

About cycle basis

A graph has many cycles. Given several cycles, we can take edge-wise XOR (exclusive OR) (where common edges are cancelled out) to obtain a new cycle (or possibly multiple cycles). Thus, if we enumerate some “fundamental” cycles, other cycles may be represented as their combinations. The “set of fundamental cycles” are a called cycle basis.

Definition of cycle space and cycle basis

Consider a graph \(G=(V,E)\). The set \(\mathcal{C}(G)\) of subgraphs of \(G\) whose degrees are all even is called its cycle basis.

One can naturally define the XOR operation on the elements of \(\mathcal{C}(G)\). Namely, for \(H_1,H_2\in \mathcal{C}(G)\), if you define \(H_1\oplus H_2\) as “the subgraph of \(G\) whose edge set is formed by the edges contained in exactly one of \(H_1\) and \(H_2\),” then \(H_1\oplus H_2\in \mathcal{C}(G)\). (\(\mathcal{C}(G)\) is a group with respect to \(\oplus\); the identity element is the empty graph, and the inverse is itself.)

A set \(\mathcal{B}\) of simple cycles, that is a subset of \(\mathcal{C}(G)\), is called a cycle basis when the following are satisfied. (This is analogous to an XOR basis on a vector space on \(\mathbb{F}_2\).)

1. Any \(C\in \mathcal{C}(G)\) can be represented as the XOR (\(\oplus\)) of cycles in \(\mathcal{B}\).
2. Any cycle in \(\mathcal{B}\) cannot be represented as the XOR of other cycles in \(\mathcal{B}\).

---

We will state several facts.

Fact 1.

A cycle basis \(\mathcal{B}\) can be obtained by the following procedure.

1. Take a spanning tree \(T\) of \(G\).
2. For each edge \(e=(u,v)\) of \(G\) not contained in \(T\), add \(C_e=P\cup\lbrace e\rbrace\) to \(\mathcal{B}\), where \(P\) is the simple path from \(u\) to \(v\) on \(T\).

Fact 2.

The size of a cycle basis is \(|E|-|V|+1\), which is clear from the aforementioned procedure of obtaining a cycle basis.

Fact 3.

Any simple cycle contained in \(G\) is contained in \(\mathcal{C}(G)\), and there are at most \(2^{|E|-|V|+1}\) such cycles.

Fact 4.

There are at most \(2^{|E|-|V|+1}\) simple paths connecting vertices \(s\) and \(t\) \((s,t\in V)\).

(Proof)
Fix an \(s\text{-}t\) simple path \(P_0\). For an \(s\text{-}t\) simple path \(P\), \(P\oplus P_0\) is an element of \(\mathcal{C}(G)\). For different \(s\text{-}t\) simple paths \(P_1\) and \(P_2\), we have \(P_0\oplus P_1\neq P_0\oplus P_2\), so the number of the \(s\text{-}t\) simple paths is at most \(|\mathcal{C}(G)|= 2^{|E|-|V|+1}\).

---

Solution for the original problem

We introduce a solution that utilizes Fact 4. Let \(K\) be \(M-N+1\), the size of a cycle basis.

If we ignore the computational complexity, the following code obtains the right answer. (G is the adjacency list.)

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)

In this code, the dfs (Depth-First Search) function is called at most \(N2^K\) times.

(Proof: dfs is called as many times as the number of simple paths from vertex \(1\). By Fact 4, there are at most \(2^K\) simple paths between \(1\text{-}v\), so dfs is called at most \(N2^K\) times in total.)

This will not finish in time because the size of the graph is large, but the size can be reduced by contracting the graph.

First of all, any vertex \(v\ (v\neq 1,N)\) of degree \(1\) can be deleted, because it is not contained in any \(1 \text{-}N\). For the graph has no degree-\(1\) vertex other than vertex \(1\) and \(N\), create a new graph \(H\) whose vertex set is \(S=\lbrace 1,N\rbrace\cup \lbrace v\mid \mathrm{deg}[v]\geq 3\rbrace\). Any vertex not contained in \(S\) has a degree \(2\), so simple paths can be contracted. In other words, for \(u,v\in S\), every time you find a \(u\text{-}v\) simple path that does not contain a vertex in \(S\) in the middle, replace the simple path with a weighted edge and add to \(H\) (where the weight is the length of the path). Since \(H\) has at most \(2K+2\) vertices and \(3K+1\) edges, one can perform the same DFS as above on this graph \(H\) to solve the original problem in \(O(N+K2^K)\) time.

---

Alternatively, the problem can be solved as follows: Take a cycle basis so that we can enumerate all elements of \(\mathcal{C}(G)\). Fix an arbitrary \(1\text{-}N\) simple path \(P_0\), and check for each \(C\in \mathcal{C}(G)\) if \(P_0\oplus C\) is a simple path.

This solution also requires to reduce the size of the graph. After the contraction, there are at most \(3K+1\leq 64\) edges, so the edges contained in \(P_0\) or a cycle in \(\mathcal{C}(G)\) can be represented by a 64-bit integer. If one can determine in \(O(K)\) time for each \(C\in \mathcal{C}(G)\) the 64-bit-integer representation of \(C\) and whether \(P_0\oplus C\) and \(1\text{-}N\) is a simple path, the same computational complexity \(O(N+K2^K)\) can be achieved.

---

Sample code (DFS approach)

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:])