Minimum-cost Flow
题号：NC209437
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Bobo has a network of nodes and arcs. The -th arc goes from the -th node to the -th node, with cost .

Bobo also asks questions. The -th question is specified by two integers and , which is to ask the minimum cost to send one unit of flow from the -th node to the -th node, when all the edges have capacity (a fraction).

You can refer the wiki page for further information of Minimum-cost Flow.

输入描述:

The input consists of several test cases terminated by end-of-file.

The first line of each test case contains two integers n and m. The i-th of the following m lines contains three integers a_i, b_i and c_i. The next line contains an integer q. The i-th of the last q lines contains two integers u_i and v_i.

* 
* 
* 
* 
* 
* , 
* The sum of m does not exceed .
* The sum of q does not exceed .

输出描述:

For each test case, print q fractions (or `NaN`, if it is impossible to send one unit of flow) which denote the answer.
示例1

输入

复制 
2 1
1 2 2
1
1 1
2 2
1 2 1
1 2 2
3
1 2
2 3
1 4

输出

复制 
2/1
3/2
4/3
NaN