Simple Graph Paths Sum

You are given a connected, simple undirected graph with n vertices and m edges. Each edge has a positive integer weight. Initially, the graph satisfied a beautiful property: for any two simple cycles (i.e. cycles that do not repeat any vertex), the sum of the weights of the edges in each cycle was the same (i.e. if you take any simple cycle, its weight sum equals some constant \(K\)).

However, some of the edge weights are modified arbitrarily, and the property may no longer hold.

You are then given q queries. Each query consists of two vertices \(S\) and \(T\). For each query, you must compute the sum over all simple paths from \(S\) to \(T\) of the total weight of each path. A simple path is defined as a path that does not revisit any vertex. Since the answer can be very large, output it modulo \(998244353\).

Input Format: The first line contains three integers \(n, m, q\) denoting the number of vertices, edges, and queries, respectively. Then follow m lines, each containing three integers \(u, v, w\) representing an edge between vertices \(u\) and \(v\) with weight \(w\). Finally, there are q lines, each with two integers \(S, T\), representing a query.

Note: The graph is simple (no multiple edges or self-loops) and undirected.

inputFormat

The input begins with a line containing three integers: \(n\) \(m\) \(q\).

This is followed by \(m\) lines, each containing three integers \(u\) \(v\) \(w\), indicating there is an undirected edge between \(u\) and \(v\) with weight \(w\).

Then \(q\) lines follow, each containing two integers \(S\) and \(T\), the query endpoints.

It is guaranteed that \(1 \leq n \leq 10\) so that enumerating all simple paths is feasible.

outputFormat

For each query, output one line containing a single integer, which is the sum of the weights (each path's weight is defined as the sum of the weights on that path) over all simple paths from \(S\) to \(T\), taken modulo \(998244353\).

sample

3 3 1
1 2 1
2 3 2
1 3 3
1 3

6