This problem asks to find “the number of paths,” which may have puzzled some of you. However, you can actually use Depth-First Search (DFS) that appeared in Problem C to solve this problem with a simple algorithm.
Specifically, implement a DFS that is expressed by the following pseudo-Python code. (Note the usage of the flag variable vis differs from an ordinary dfs.)

# g : The adjacecy list of graph, where the indices of vertices is subtracted by 1

vis = [False] * N
path = []
answer = 0
limit = 1000000
path = []

def dfs(c):
  if answer == limit:
    return

  vis[c] = True
  path.append(c)
  answer += 1
  
  for d in g[c]:
    if vis[d] == False:
      dfs(d)

  vis[c] = False
  path.pop()

dfs(0)

In this DFS, each state corresponds to each path. Specifically, the path represented by the sequence of vertices stored in path in the DFS corresponds to a state of DFS.

• Here, a “state” refers to a vertex when the process of transitions of DFS is represented as a rooted tree. Also, one can show by induction that a state and a path corresponds one-to-one.

Therefore, the answer is the number of states that the DFS visits, which can be counted by actually executing the DFS. If the number of paths exceed \(10^6\), we stop the DFS and determine that the answer is \(10^6\).

What about the complexity? The function dfs in the pseudocode is called at most \(10^6\) times, and the complexity inside dfs is bounded by \(\mathrm{deg}(c)\), the degree of vertex \(c\). Since the degree of each vertex is at most \(10\), the number of steps is bounded by an order of \(10^6 \times 10 = 10^7\). Thus, this algorithm executes fast enough to get AC (accepted).

• Sample code (C++)

#include <iostream>
#include <vector>
using namespace std;

int calc(int N, vector<vector<int>> g) {
  int ans = 0, limit = 1000000;
  vector<int> vis(N);
  auto dfs = [&](auto rc, int c) -> void {
    if (ans == limit) return;
    ans++;
    vis[c] = true;
    for (auto& d : g[c]) {
      if (vis[d]) continue;
      rc(rc, d);
    }
    vis[c] = false;
  };
  dfs(dfs, 0);
  return ans;
}

int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<int>> g(N);
  for (int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  cout << calc(N, g) << "\n";
}