회로

지제냐는 학교 물리 실습 시간에 전기를 공부한다. 그의 다음 과제는 전기 회로망을 분석하는 것이다.

전기 회로망은 선으로 연결된 노드의 집합이다. 노드 중 하나는 소스 노드이고, 다른 하나는 싱크 노드이다. 이 문제의 회로망은 올바른 회로망이다.

회로망은 다음 규칙으로 만들 수 있으면 올바르다.

• 소스 노드와 싱크 노드가 선 하나로 연결된 기본 회로망은 올바르다.
• 올바른 회로망 A, B가 있을 때, A의 싱크 노드와 B의 소스 노드를 합친 회로망 S(A, B)는 올바르다. 결과 회로망의 소스 노드는 A의 소스 노드이고, 싱크 노드는 B의 싱크 노드이다.
• 올바른 회로망 A, B가 있을 때, A와 B의 소스 노드를 합치고 A와 B의 싱크 노드도 합친 회로망 P(A, B)는 올바르다. 결과 회로망의 소스 노드는 합쳐진 소스 노드이고, 싱크 노드는 합쳐진 싱크 노드이다.
• 올바른 회로망은 모두 기본 회로망에서 위의 두 규칙을 유한번 적용해 만들 수 있다.

지제냐는 일부 선을 제거해 남은 선들이 트리를 이루는 방법의 수를 세려고 한다. 트리란 임의의 두 노드 사이에 선을 따라 가는 경로가 정확히 하나 있는 그래프이다.

방법의 수를 $998\,244\,353$으로 나눈 나머지를 구하라.

첫 줄에 두 정수 $n$, $m$이 주어진다. 각각 노드의 수와 선의 수이다 ($1 \le n,m \le 100\,000$).

이어지는 $m$개의 줄에는 정수 $a$, $b$가 주어지며, 이는 노드 $a$와 $b$가 선으로 연결되어 있다는 뜻이다 ($1 \le a, b \le n$; $a \ne b$).

주어진 회로망은 올바른 회로망이다. 소스 노드는 1번, 싱크 노드는 n번 노드이다. 올바른 회로망에서는 같은 노드 쌍 사이에 선이 여러 개 있을 수 있다.

남은 선들이 트리를 이루도록 선을 제거하는 방법의 수를 $998\,244\,353$으로 나눈 나머지로 한 줄에 출력한다.

첫 번째와 세 번째 예제에서는 선을 어느 하나든 제거할 수 있다.

두 번째 예제에서는 선 (1, 6)과 다른 선 하나를 제거할 수 있다. 또는 1-2-4-6 사슬과 1-3-5-6 사슬에서 선을 하나씩 제거할 수 있다.