Minimum Cut Between Two Vertices

Given an undirected connected graph with \(n\) vertices and \(m\) edges, where each edge has a cutting cost, answer \(q\) queries of the following type: For two given vertices \(s\) and \(t\), compute the minimum cut between them.

The minimum cut between two vertices is defined as the minimum total cost of edges that must be removed so that the vertices become disconnected. By the max-flow min-cut theorem, this value equals the maximum flow between vertices \(s\) and \(t\).

Note that every undirected edge is interpreted as two directed edges with the same capacity.

inputFormat

The first line contains three integers (n), (m) and (q) — the number of vertices, edges, and queries respectively. Each of the next (m) lines contains three integers (u), (v) and (w), denoting an undirected edge between vertices (u) and (v) with cost (w). Each of the following (q) lines contains two integers (s) and (t), representing a query for the minimum cut between vertices (s) and (t).

outputFormat

For each query, output a single integer on a new line — the minimum cut (i.e., the maximum flow) between the given vertices.

sample

4 5 3
1 2 4
2 3 3
3 4 2
4 1 1
2 4 5
1 3
2 4
1 4

4
7
5