給定一個簡單連通無向圖，它是一個仙人掌圖（cactus）：每條邊至多屬於一個簡單環。此仙人掌圖是三角形的：任何簡單環的長度至多為 3。

請回答查詢。在每個查詢中，給定兩個頂點 $s$ 和 $f$，以及一個整數 $k$。請找出頂點 $s$ 和 $f$ 之間長度恰好為 $k$ 的簡單路徑數量。你需要將此數量對 $998\,244\,353$ 取模。

若路徑的所有頂點皆相異，則該路徑為簡單路徑；路徑的長度等於路徑上的邊數。

輸入格式

第一行包含兩個整數 $n, m$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le \frac{3(n-1)}{2}$) —— 圖中的頂點數與邊數。

接下來 $m$ 行，每行包含兩個整數 $u, v$ ($1 \le u, v \le n, u \neq v$)，表示圖中存在一條無向邊 $(u, v)$。所有邊皆不相同。保證該圖為連通的三角形仙人掌圖。

下一行包含一個整數 $q$ ($1 \le q \le 2 \cdot 10^5$) —— 查詢的數量。

接下來 $q$ 行，每行包含三個整數 $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