27091번 - 영어 시간

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

짝짓기 문제는 왼쪽과 오른쪽에 각각 세로로 $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$)