Cycle

AtCoder

IDfps_24_w

Time5000ms

Memory256MB

Difficulty—

You are given a simple undirected graph $G$ with $N$ vertices and $M$ edges, where the vertices are numbered $1$ through $N$. The $i$\-th edge connects vertex $A_i$ and vertex $B_i$. Among all spanning subgraphs of $G$(that is, subgraphs covering all vertices of $G$), count how many satisfy the following condition, and output the result modulo $998244353$: * There exists a cycle that contains both vertex $1$ and vertex $N$. ## Constraints * $3 \leq N \leq 16$ * $3 \leq M \leq \binom{N}{2}$ * $1 \leq A_i < B_i \leq N$ * If $i \neq j$, then $(A_i, B_i) \neq (A_j, B_j)$ * All input values are integers ## Input The input is given from standard input in the following format: $N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_M$ $B_M$ ## Partial Score This problem has partial scoring: * If you solve all datasets with $N \leq 10$, you will earn $4$ points. [samples]

Samples

Input #1

Output #1

8

For example, the spanning subgraph consisting of edges $1$, $2$, $3$, and $5$ satisfies the condition, because edges $2$, $3$, and $5$ form a cycle that contains both vertex $1$ and vertex $4$.

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Cycle",
    "description": {
      "content": "You are given a simple undirected graph $G$ with $N$ vertices and $M$ edges, where the vertices are numbered $1$ through $N$.   The $i$\\-th edge connects vertex $A_i$ and vertex $B_i$.   Among all spa",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "fps_24_w"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a simple undirected graph $G$ with $N$ vertices and $M$ edges, where the vertices are numbered $1$ through $N$.  \nThe $i$\\-th edge connects vertex $A_i$ and vertex $B_i$.  \nAmong all spa...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments