삼각 캑터스 경로

간선이 많아야 하나의 단순 사이클에 속하는 단순 연결 무방향 그래프가 주어진다. 이를 캑터스라고 한다. 이 캑터스는 삼각 캑터스이며, 임의의 단순 사이클의 길이는 $3$ 이하이다.

각 질의에서는 두 정점 $s$, $f$와 정수 $k$가 주어진다. 정점 $s$에서 $f$까지 길이가 정확히 $k$인 단순 경로의 개수를 구하라. 답은 $998\,244\,353$으로 나눈 나머지로 구한다.

경로가 단순하다는 것은 경로 위의 모든 정점이 서로 다르다는 뜻이다. 경로의 길이는 경로에 포함된 간선의 수와 같다.

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

다음 $m$개 줄에는 각각 무방향 간선 $(u, v)$를 나타내는 두 정수 $u$, $v$ ($1 \leq u, v \leq n$, $u \neq v$)가 주어진다. 모든 간선은 서로 다르다. 주어지는 그래프는 연결된 삼각 캑터스임이 보장된다.

다음 줄에는 질의의 개수 $q$ ($1 \leq q \leq 2 \cdot 10^5$)가 주어진다.

다음 $q$개 줄에는 각각 질의를 나타내는 세 정수 $s$, $f$, $k$ ($1 \leq s, f \leq n$, $0 \leq k < n$)가 주어진다.

$q$개의 정수를 출력한다. 각 정수는 해당 질의의 답이다.