Road Expansion Plan

The city of Pordenone is planning an expansion of its road network. There are $N$ towns (clearly indexed from $0$ to $N-1$) in Pordenone’s hinterland and $M$ bidirectional roads connecting some pairs of towns.

An expansion plan is any set of roads that contains the currently present roads. E. Domora, the mayor of Pordenone, cannot choose an expansion plan among all the possible ones and is in desperate need of your analytical skills.

A cluster $C$ of towns is a non-empty set of towns such that, for each $t \in C$ and any other town $u$, there exists a set of roads connecting (possibly indirectly) $t$ and $u$ if and only if $u \in C$. Note that, given a road network, there is an unique way to partition the towns in clusters.

Task

Given a road network, its Scoazza™ Score is $2^k$, where $k$ is the number of clusters in which it partitions the towns; Mayor Domora is asking you to compute the sum of the Scoazza™ Scores of all possible expansion plans.

Since this number can be big, output it modulo $998 \ 244 \ 353$.

Input data

The input file consists of:

• a line containing integers $N$, $M$.
• a line containing the $M$ integers $U_0, \dots, U_{M−1}$.
• a line containing the $M$ integers $V_0, \dots, V_{M−1}$.

Output data

The output file must contain a single line consisting of a single integer: the answer to the problem.

Constraints and clarifications

• $1 \leq N \leq 100 \ 000$
• $1 \leq M \leq 200 \ 000$
• $0 \leq U_i,V_i < N$ for each $0 \leq i \leq M-1$
• All the roads are distinct.

Example 1

stdin

4 3
0 1 2
1 2 0

stdout

18

Explanation

There are $4$ towns and $3$ roads already built:

1. The road connecting town $0$ and town $1$.
2. The road connecting town $1$ and town $2$.
3. The road connecting town $2$ and town $0$.

There are $3$ possible roads that can be built:

1. The road connecting town $0$ and town $3$.
2. The road connecting town $1$ and town $3$.
3. The road connecting town $2$ and town $3$.

There are $8$ possible expansion plans:

1. The one in which no road is added. In this case there will be $2$ clusters: $0, 1, 2$ and $3$.
2. The one in which only the road connecting towns $0$ and $3$ is added. In this case there will be a single cluster: $0, 1, 2, 3$.
3. etc.

Note that, following any other expansion plan will lead to a single cluster containing all the cities. The answer is hence $2^2 + 2^1 + 2^1 + 2^1 + 2^1 + 2^1 + 2^1 + 2^1 = 18$.

Example 2

stdin

10 8
0 1 2 3 7 6 4 8
1 2 0 4 5 7 9 9

stdout

360988397

Explanation

There are $10$ towns and $8$ roads already built: