H. Triangular Cactus Paths
time limit per test
2 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

You are given a simple connected undirected graph that is a cactus: each edge lies on at most one simple cycle. This cactus is triangular: the length of any simple cycle is at most $$$3$$$.

Answer the queries. In each query, you are given two vertices $$$s$$$ and $$$f$$$, and an integer $$$k$$$. Find the number of simple paths between vertices $$$s$$$ and $$$f$$$ with length exactly $$$k$$$. You should find this number modulo $$$998\,244\,353$$$.

The path is simple if all its vertices are different, the length of the path is equal to the number of edges on the path.

Input

The first line contains two integers $$$n$$$, $$$m$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$n - 1 \leq m \leq \frac{3(n-1)}{2}$$$) — the number of vertices and edges in the graph.

Each of the next $$$m$$$ lines contains two integers $$$u$$$, $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), meaning that there is an undirected edge $$$(u, v)$$$ in the graph. All edges are different. It is guaranteed that the graph is a connected triangular cactus.

The next line contains a single integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — the number of queries.

Each of the next $$$q$$$ lines contains three integers $$$s$$$, $$$f$$$, $$$k$$$ ($$$1 \leq s, f \leq n$$$, $$$0 \leq k \lt n$$$) — the description of a query.

Output

Print $$$q$$$ integers — the answers to the queries.

Example
Input
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
Output
1
0
1
2
1
0