Background

This is a template problem. Before solving it, please make sure you know Dinic or ISAP. If you brute-force your way through, I will ask you to smoke.

By convention, network flow problems do not allow testdata that hacks Dinic/ISAP, but they may hack EK. The testdata for this problem strictly follows the rule above.

Problem Description

Given an undirected connected graph with $n + 1$ vertices and $m$ edges, labeled from $0$ to $n$, answer multiple queries asking for the minimum cut between two vertices.

The minimum cut between two vertices is defined as follows: each edge in the original graph has a cost to cut it, and you need to make the two vertices disconnected with the minimum total cost.

Input Format

The first line contains two integers $n, m$.

The next $m$ lines each contain three integers $u, v, w$, indicating an undirected edge between $u$ and $v$, with cutting cost $w$.

The next line contains an integer $Q$, the number of queries.

The next $Q$ lines each contain two integers $u, v$. You need to compute the minimum cut between $u$ and $v$.

Output Format

Output $Q$ lines. Each line contains one integer, the answer to the corresponding query.

3 5
0 1 2
1 2 2
3 1 3
3 2 1
0 2 1
3
0 3
1 3
1 2

3
4
4

Hint

Constraints: $1 \le n \le 500$, $0 \le m \le 1500$, $0 \le Q \le 10^5$, $0 \le w \le 10^4$, and $u \neq v$.

Translated by ChatGPT 5