Just one

AtCoder

IDabc226_e

Time2000ms

Memory256MB

Difficulty—

Given is an undirected graph with $N$ vertices and $M$ edges. The vertices are called Vertex $1$, Vertex $2$, $\ldots$, Vertex $N$, and the edges are called Edge $1$, Edge $2$, $\ldots$, Edge $M$. Edge $i$ $(1 \leq i \leq M)$ connects Vertex $U_i$ and Vertex $V_i$. It is guaranteed that the graph is simple: it has no self-loops and no multi-edges. There are $2^M$ ways to direct every edge in this graph. We want each vertex to have exactly one edge going from that vertex to another vertex. How many ways are there to direct the edges in that way? Since the answer may be enormous, print it modulo $998244353$. ## Constraints * $2 \leq N \leq 2\times 10^5$ * $1 \leq M \leq 2\times 10^5$ * $1 \leq U_i,V_i \leq N$ * $U_i \neq V_i$ * All values in input are integers. * The given graph is simple. ## Input Input is given from Standard Input in the following format: $N$ $M$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_M$ $V_M$ [samples]

Samples

Input #1

Output #1

2

There are two ways to direct the edges to achieve the objective:

*   $1\rightarrow 2$ , $2\rightarrow 3$ , $1\leftarrow 3$
*   $1\leftarrow 2$ , $2\leftarrow 3$ , $1\rightarrow 3$

Input #2

2 1
1 2

Output #2

0

It is obviously impossible to make every vertex have one edge going from that vertex.

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Just one",
    "description": {
      "content": "Given is an undirected graph with $N$ vertices and $M$ edges. The vertices are called Vertex $1$, Vertex $2$, $\\ldots$, Vertex $N$, and the edges are called Edge $1$, Edge $2$, $\\ldots$, Edge $M$. Edg",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc226_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given is an undirected graph with $N$ vertices and $M$ edges. The vertices are called Vertex $1$, Vertex $2$, $\\ldots$, Vertex $N$, and the edges are called Edge $1$, Edge $2$, $\\ldots$, Edge $M$. Edg...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments