codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1093D.md (2078B)


      1 Source: https://codeforces.com/problemset/problem/1093/D
      2 
      3 D. Beautiful Graph
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given an undirected unweighted graph consisting of $n$ vertices and $m$ edges.
     22 
     23 You have to write a number on each vertex of the graph. Each number should be $1$, $2$ or $3$. The graph becomes beautiful if for each edge the sum of numbers on vertices connected by this edge is odd.
     24 
     25 Calculate the number of possible ways to write numbers $1$, $2$ and $3$ on vertices so the graph becomes beautiful. Since this number may be large, print it modulo $998244353$.
     26 
     27 Note that you have to write exactly one number on each vertex.
     28 
     29 The graph does not have any self-loops or multiple edges.
     30 
     31 Input
     32 
     33 The first line contains one integer $t$ ($1 \le t \le 3 \cdot 10^5$) — the number of tests in the input.
     34 
     35 The first line of each test contains two integers $n$ and $m$ ($1 \le n \le 3 \cdot 10^5, 0 \le m \le 3 \cdot 10^5$) — the number of vertices and the number of edges, respectively. Next $m$ lines describe edges: $i$-th line contains two integers $u_i$, $ v_i$ ($1 \le u_i, v_i \le n; u_i \neq v_i$) — indices of vertices connected by $i$-th edge.
     36 
     37 It is guaranteed that $\sum\limits_{i=1}^{t} n \le 3 \cdot 10^5$ and $\sum\limits_{i=1}^{t} m \le 3 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test print one line, containing one integer — the number of possible ways to write numbers $1$, $2$, $3$ on the vertices of given graph so it becomes beautiful. Since answers may be large, print them modulo $998244353$.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 2
     49 2 1
     50 1 2
     51 4 6
     52 1 2
     53 1 3
     54 1 4
     55 2 3
     56 2 4
     57 3 4
     58 ```
     59 
     60 Output
     61 
     62 ```
     63 4
     64 0
     65 ```
     66 
     67 Note
     68 
     69 Possible ways to distribute numbers in the first test:
     70 
     71 1. the vertex $1$ should contain $1$, and $2$ should contain $2$;
     72 2. the vertex $1$ should contain $3$, and $2$ should contain $2$;
     73 3. the vertex $1$ should contain $2$, and $2$ should contain $1$;
     74 4. the vertex $1$ should contain $2$, and $2$ should contain $3$.
     75 
     76 In the second test there is no way to distribute numbers.