알고리즘이 적용되었다

연결된 무방향 그래프가 $n$개의 정점으로 주어진다. 이 그래프를 시작 그래프라고 하자.

세 정수 $(a, b, c)$ ($1 \leq a < b < c \leq n$)가 다음 세 조건을 모두 만족하면 이 튜플을 좋은 튜플이라고 한다.

1. 정점 $a$와 $b$가 간선으로 연결되어 있다.
2. 정점 $a$와 $c$가 간선으로 연결되어 있다.
3. 정점 $b$와 $c$가 간선으로 연결되어 있지 않다.

시작 그래프에 다음 알고리즘을 적용했다. 좋은 튜플이 존재하는 동안 임의의 좋은 튜플 $(a, b, c)$를 골라 정점 $b$와 $c$ 사이에 간선을 추가한다. 이렇게 얻은 그래프를 완성 그래프라고 한다. 매 단계에서 어떤 좋은 튜플을 고르더라도 완성 그래프는 같다는 것을 증명할 수 있다.

시작 그래프가 주어졌을 때, 완성 그래프를 $n$가지 색으로 칠하는 방법의 수를 구하라. 색칠은 인접한 두 정점이 같은 색을 갖지 않도록 각 정점에 색을 배정하는 것이다. 더 형식적인 정의가 필요하면 D번 문제를 참고하라.

첫 줄에 정점 수 $n$과 간선 수 $m$이 주어진다. ($2 \leq n \leq 3 \cdot 10^5$, $1 \leq m \leq 3 \cdot 10^5$)

다음 $m$개의 줄에는 간선의 두 끝점 $u$와 $v$가 주어진다. ($1 \leq u < v \leq n$)

주어진 그래프는 연결되어 있고 다중 간선이 없다고 보장된다.

완성 그래프를 $n$가지 색으로 칠하는 방법의 수를 $998244353$으로 나눈 나머지를 출력한다.

실제 답을 $y$, 출력한 값을 $x$라고 하자. $-2^{63} \leq x < 2^{63}$이고 $x-y$가 $998244353$으로 나누어떨어지면 정답으로 인정한다.

첫 번째 예시에서 시작 그래프는 다음과 같다.

좋은 튜플은 $(1, 2, 3)$뿐이므로 간선 $2$-$3$이 추가된다.

이 그래프를 3가지 색으로 칠하는 방법은 6가지이다.