City Under Current#3269

City Under Current

1 secondo

64 megabyte

Media

The mayor of Bitberg has decided to establish electrical connections between some houses in the city. Each connection involves installing a cable with a specific resistance $R$ between two houses. These cables are bidirectional, allowing current to flow in both directions between the connected houses. It is guaranteed that the network of cables forms a connected graph, ensuring that there is at least one path between any pair of houses. After the installation, Mr. 01101 (the mayor of Bitberg) was approached by the fire department to verify that the resistance between certain pairs of houses does not exceed the specified resistance limits. Your task is to assist the firefighters by quickly determining whether the resistance between several pairs of houses is within the acceptable range.

Input

The houses are numbered from $1$ to $N$ ( $N \leq 100$ N \leq 100). The connections are described by $M$ pairs $(u, v)$ , where $M \leq 10000$ M \leq 10000. Additionally, you are provided with a matrix $A$ of size $N \times N$ N \times N, which specifies the maximum allowable resistance between any two houses, and a matrix $B$ that specifies the minimum allowable resistance. The diagonal elements $A_{ii}$ A_{ii} and $B_{ii}$ B_{ii} are always $- 1$ , indicating no restrictions on the resistance between a house and itself. Both matrices $A$ and $B$ are symmetric, meaning $A_{ij} = A_{j i}$ A_{ij} = A_{ji} and $B_{ij} = B_{j i}$ B_{ij} = B_{ji}. The values satisfy $0 \leq A_{ij}, B_{ij} \leq 1 0^{6}$ 0 \leq A_{ij}, B_{ij} \leq 10^6.

The firefighters' queries are given as pairs $(u, v)$ , where they request the resistance between two houses. There are $Q$ queries in total ( $Q \leq 10$ Q \leq 10).

The input begins with three integers $N$ , $M$ , and $Q$ . The next $M$ lines each contain two numbers $u$ and $v$ , representing a cable with resistance between houses $u$ and $v$ ( $1 \leq u, v \leq N$ 1 \leq u, v \leq N). Following this, $N$ lines each contain $N$ numbers, where the $j$ -th element in the $i$ -th row corresponds to $A_{ij}$ A_{ij}. Another $N$ lines follow, each containing $N$ numbers, where the $j$ -th element in the $i$ -th row corresponds to $B_{ij}$ B_{ij}. Finally, the next $Q$ lines each contain two numbers $(u, v)$ ( $1 \leq u, v \leq N$ 1 \leq u, v \leq N), representing the firefighters' queries about the resistance between houses $u$ and $v$ .

Output

For each of the $Q$ queries, output a line containing either "Yes" (without quotes) if the resistance between the houses is within the allowed limits, along with the resistance value to a precision of $1 0^{- 7}$ 10^{-7}, or "No" (without quotes) if the resistance does not meet the specified conditions.

Esempi

Esempio 1