영어 시간

브루는 영어 시간에 아래와 같은 형태의 짝짓기 문제를 받았다.

짝짓기 문제는 왼쪽과 오른쪽에 각각 세로로 $N$개의 점이 놓인 상태에서 푼다. 정확히는, $1 \le i \le N$인 모든 정수 $i$에 대해 좌표평면의 $(1, i)$와 $(2, i)$에 점이 하나씩 찍혀 있다고 생각해도 좋다.

각 점 옆에는 보기가 쓰여 있다. $(1, i)$ 점 옆의 보기에는 단어가, $(2, i)$ 점 옆의 보기에는 그 뜻이 영어로 쓰여 있다. 단어와 뜻이 일치하는 두 점을 선분으로 잇는다. 문제를 올바르게 풀면 모든 점이 정확히 하나의 선분의 끝점이 되고, 모든 선분은 한쪽 끝점의 $x$좌표가 $1$, 반대쪽 끝점의 $x$좌표가 $2$이다.

브루는 최대한 문제를 풀어 보았지만, $N$개 선분 중 $K$개밖에 찾지 못했다. 그래서 남은 점들을 선분으로 이어 올바른 답안이 되도록 연결했다.

남은 점들을 어떻게 이을지 고민하던 브루는 답안의 최종 형태가 아름다운 답안이 되도록 점을 이으려고 한다.

올바른 답안이란, 아래 두 조건을 만족하는 답안을 뜻한다.

• 모든 선분은 $1 \le i, j \le N$에 대해 $(1, i)$와 $(2, j)$를 끝점으로 한다. (단, $i$, $j$는 정수)
• $2N$개의 점은 모두 정확히 하나의 선분의 끝점이 된다.

아래 그림은 올바른 답안과 올바르지 않은 답안의 예시이다.

올바른 답안	올바르지 않은 답안	올바르지 않은 답안

아름다운 답안이란, 올바른 답안 중에서 아래 두 조건을 추가로 만족하는 답안을 뜻한다.

• 세 선분 이상이 한 점에서 만나지 않는다.
• 선분들로 둘러싸인 닫힌 영역이 존재하지 않는다. 다시 말해, 주어진 선분들의 부분선분만을 이용해 넓이가 양수인 다각형을 만들 수 없다.

아래 그림은 아름다운 답안과 아름답지 않은 답안의 예시이다.

아름다운 답안	아름답지 않은 답안	아름답지 않은 답안

브루는 현재 이은 선분들을 그대로 두고, 아직 연결하지 않은 나머지 점들을 이어 만들 수 있는 아름다운 답안의 가짓수를 구하려 한다.

첫 줄에 두 정수 $N$과 $K$가 주어진다.

둘째 줄부터 $K+1$번째 줄까지는 브루가 이은 선분의 정보가 주어진다. 각 줄에는 두 정수 $U_i$, $V_i$가 띄어쓰기를 사이에 두고 주어진다. 이는 $(1, U_i)$와 $(2, V_i)$가 선분으로 이어졌다는 뜻이다.

나머지 점들을 선분으로 연결했을 때 만들 수 있는 올바른 답안의 가짓수를 $998\ 244\ 353$으로 나눈 나머지를 출력한다.

• $3 \le N \le 2 \times 10^5$
• $0 \le K \le N$
• $1 \le U_i \le N$ ($1 \le i \le K$)
• $1 \le V_i \le N$ ($1 \le i \le K$)
• $U_i \neq U_j$ ($1 \le i < j \le K$)
• $V_i \neq V_j$ ($1 \le i < j \le K$)