Given a weighted directed graph with $n$ vertices and $m$ edges, the two endpoints of each edge are generated uniformly and independently at random from the $n$ vertices, and the edge weights are generated uniformly and independently at random from $[0, 2^{32})$.
You are also given $q$ queries, each consisting of two endpoints $s_i$ and $t_i$. You need to find the minimum path weight sum from $s_i$ to $t_i$. If no such path exists, output $-1$.
It is guaranteed that the $s_i$ and $t_i$ for the $q$ queries are chosen uniformly and independently at random from all vertices, and are independent of the graph generation.
Note that the vertices are numbered $1 \sim n$, and the graph may contain multiple edges and self-loops.
Input
The first line contains four integers $n, m, q, seed$, where $seed$ is an integer chosen uniformly at random from $[0, 2^{32})$ used to generate the graph. Participants can generate the required graph using the code provided at the end of the problem.
The next $q$ lines each contain two positive integers $s_i$ and $t_i$, representing a query.
It is guaranteed that the $s_i$ and $t_i$ for the $q$ queries are chosen uniformly and independently at random from all vertices, and are independent of the graph generation.
Output
Output $q$ lines, each containing an integer representing the answer.
Examples
Input 1
4 8 5 1112792816 2 3 4 3 4 3 3 2 1 4
Output 1
3419197189 1798364963 1798364963 3986398077 2337967903
Note
The following is the graph corresponding to the sample:
For all data: $1 \leq n \leq 2 \times 10^5, 1 \leq m \leq 3\times 10^6, 1 \leq q \leq 10^4$.
| Subtask ID | Data Range | Score |
|---|---|---|
| 1 | $n, m, q \leq 2 \times 10^3$ | $5$ |
| 2 | $n \leq 3 \times 10^3$ | $15$ |
| 3 | $m \leq n$ | $10$ |
| 4 | $m \leq 2.5 \times n$ | $20$ |
| 5 | $m \leq 5 \times 10^5$ | $20$ |
| 6 | $n \leq 10^5$ | $10$ |
| 7 | None | $20$ |
Graph generator:
#include<tuple>
#include<vector>
#include<random>
std::vector<std::tuple<int, int, long long>> generate_edges(int n, int m, unsigned seed) {
std::mt19937 gen(seed);
std::vector<std::tuple<int, int, long long>> edges(m);
unsigned max = -1u / n * n;
auto sample = [&]() {
unsigned x;
do { x = gen(); } while(x >= max);
return x % n + 1;
};
for(auto & [u, v, w] : edges) {
u = sample();
v = sample();
w = gen();
} // Edge from u to v with weight w
return edges;
}If you do not understand this code, you can assume that mt19937 is a relatively strong pseudo-random number generator. The graph generated by this code can be considered an independently and uniformly generated random graph under normal circumstances. It stores an edge as a tuple and returns a vector containing $m$ edges.