単純な連結無向グラフであるサボテン（cactus）が与えられます。サボテンとは、各辺が高々1つの単純サイクルに含まれるグラフのことです。このサボテンは三角形（triangular）であり、任意の単純サイクルの長さは高々3です。

クエリに答えてください。各クエリでは、2つの頂点 $s$ と $f$、および整数 $k$ が与えられます。頂点 $s$ から $f$ への長さがちょうど $k$ である単純パスの数を求めてください。この数は $998\,244\,353$ で割った余りを求めてください。

パスが単純であるとは、すべての頂点が異なり、パスの長さがパス上の辺の数と等しいことを指します。

入力

1行目には、グラフの頂点数と辺数を表す2つの整数 $n, m$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le \frac{3(n-1)}{2}$) が与えられます。

続く $m$ 行の各行には、グラフの無向辺を表す2つの整数 $u, v$ ($1 \le u, v \le n, u \neq v$) が与えられます。すべての辺は異なります。グラフは連結な三角形サボテンであることが保証されています。

次の行には、クエリの数を表す整数 $q$ ($1 \le q \le 2 \cdot 10^5$) が与えられます。

続く $q$ 行の各行には、クエリの内容を表す3つの整数 $s, f, k$ ($1 \le s, f \le n, 0 \le k < n$) が与えられます。

出力

$q$ 個の整数を出力してください。各整数は対応するクエリの答えです。

入出力例

入力 1

8 10
1 2
2 3
3 1
3 4
4 5
5 6
6 4
4 7
7 8
8 4
6
1 1 0
1 1 1
1 4 3
6 2 4
5 7 4
3 4 2

出力 1

1
0
1
2
1
0