{"problem":{"name":"Count Simple Paths","description":{"content":"You are given a simple undirected graph with $N$ vertices numbered $1$ to $N$ and $M$ edges numbered $1$ to $M$. Edge $i$ connects vertex $u_i$ and vertex $v_i$. The degree of each vertex is at most $","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc284_e"},"statements":[{"statement_type":"Markdown","content":"You are given a simple undirected graph with $N$ vertices numbered $1$ to $N$ and $M$ edges numbered $1$ to $M$. Edge $i$ connects vertex $u_i$ and vertex $v_i$. The degree of each vertex is at most $10$.  \nLet $K$ be the number of simple paths (paths without repeated vertices) starting from vertex $1$. Print $\\min(K, 10^6)$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $0 \\leq M \\leq \\min \\left(2 \\times 10^5, \\frac{N(N-1)}{2}\\right)$\n*   $1 \\leq u_i, v_i \\leq N$\n*   The given graph is simple.\n*   The degree of each vertex in the given graph is at most $10$.\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_M$ $v_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc284_e","tags":[],"sample_group":[["4 2\n1 2\n2 3","3\n\nWe have the following three paths that count. (Note that a path of length $0$ also counts.)\n\n*   Vertex $1$;\n*   vertex $1$, vertex $2$;\n*   vertex $1$, vertex $2$, vertex $3$."],["4 6\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4","16"],["8 21\n2 6\n1 3\n5 6\n3 8\n3 6\n4 7\n4 6\n3 4\n1 5\n2 4\n1 2\n2 7\n1 4\n3 5\n2 5\n2 3\n4 5\n3 7\n6 7\n5 7\n2 8","2023"]],"created_at":"2026-03-03 11:01:13"}}