# Solution 1 (`second_flight.cpp`):

For each query, we'll start by checking if that direct edge exists. If it does, we'll add that to the query's answer twice (once for morning, once for evening). Note that that edge will never be present in a path of length \(2\).

To calculate the contribution to the answer of paths with length exactly \(2\), we'll always process each query from the node with the higher degree.

For nodes with degree over \(\sqrt M\) (which we'll call "big" nodes), we can precompute the max flow to all possible indirect destinations by traversing all \(2\)-steps. This uses each of the \(M\) edges at most once per big node. As there can be at most \(\sqrt M\) such big nodes, the overall running time for the precomputation is \(\mathcal{O}(M^{1.5})\). We can later look up queries involving a big node in \(\mathcal{O}(1)\).

For nodes with degree under \(\sqrt M\) (which we'll call "small" nodes), all queries assigned to them will be between two small nodes. For each such query, we can loop through the intersection of the sets of neighbors for both nodes, directly summing the max flows in \(\mathcal{O}(\sqrt M)\) time.

Therefore, the overall running time is bounded by \(\mathcal{O}((N+M+Q)^{1.5})\).

# Solution 2 (`second_flight_alt.cpp`):

Consider the following basic algorithm for answering queries, where \(\text{adj}[a]\) is a hash table of incident edges \((a, b)\), with flight capacity \(\text{adj}[a][b] = c\):

```
def query(adj[][], x, y):
F = 0

if adj[x] contains an edge to y:
F += 2*adj[x][y] # Fly direct x -> y

for each edge (x -> mid) in adj[x]:
if adj[mid] contains edge (mid -> y):
F += min(adj[x][mid], adj[mid][y]) # Fly indirect x -> mid -> y

return F
```

Since a given \(\text{adj}[x]\) can hold \(\mathcal{O}(M)\) edges, \(Q\) queries take \(\mathcal{O}(MQ)\) for-loop steps (hash table lookups). We claim that this drops to \(\mathcal{O}((M + Q)^{1.5})\) with the two simple optimizations below:

- Memoize the answer across all unordered query pairs.
- Always process indirect flights from the query node with the lower degree.

The former means we only need to process \(\min(Q, \frac{N(N - 1)}{2})\) distinct queries. The latter means each query \((x, y)\) runs in \(\mathcal{O}(\min(d_x, d_y))\) steps, where \(d_i\) is the degree of node \(i\).

It is well known that the sum of all nodes' degrees in a simple graph is twice the number of edges. This is because a node's degree is the number of edge "endpoints" assigned to it. We can thus think of the set of degrees of all nodes as a size \(N\) partition of the \(2M\) endpoints.

The number of steps is bounded by the max possible sum of \(\min(d_x, d_y)\) over \(\min(Q, \frac{N(N - 1)}{2})\) distinct unordered query pairs \((x, y)\), for all possible degree partitions \(d_1 + ... + d_N = 2M\). Without loss of generality, assume the partitions are sorted \(d_1 \ge \cdots \ge d_N\). Thus the bound is:

\[\begin{aligned}&\begin{array}{ccccccc}\min(d_1, d_2) &+& \min(d_1, d_3) &+&\cdots&+& \min(d_1, d_N) \\ &+& \min(d_2, d_3) &+&\cdots &+& \min(d_2, d_N) \\[5pt] & & & &\ddots & & \vdots \\ & & & & &+&\min(d_{N-1}, d_N) \end{array}\\&\begin{array}{ccccccc}= d_2 &+& d_3 &+&\cdots&+& d_N \\ &+& d_3 &+&\cdots &+& d_N \\[5pt] & & & &\ddots & & \vdots & \kern{49pt}\\ & & & & &+& d_N\end{array}\end{aligned}\]

If we were to pick the \(Q\) largest terms here, we should pick the first \(k - 1\) column(s), where:

\[k = \begin{cases}O(\sqrt{Q}) &\text{if } Q \le \frac{N(N - 1)}{2} \\[5pt] N &\text{if } Q > \frac{N(N - 1)}{2} \end{cases}\]

Note that in both cases, \(k = \mathcal{O}(\sqrt{Q})\). We'll have to maximize \(1 \, d_2 + 2 \, d_3 + \cdots + (k-1)\,d_k\) by distributing \(2M\) endpoints among \(d_{1..k}\), while setting each \(d_{(k+1)..N} := 0\).

Fixing \(k\), we see that the importance of maximizing \(d_i\) increases with \(i\), as the "weights" of \(d_i\) increase with \(i\). However as \(d_i\)'s must be non-increasing, it can be shown that the max is attained when all \(d_i\)'s are equal (*). Setting each \(d_{1..k} := \frac{2M}{k}\), we get a bound of:

\[\begin{aligned}&(1 + 2 + ... + k-1)\cdot\frac{2M}{k}\\&= \frac{(k-1)(k-2)}{2} \cdot \frac{2M}{k} \\ &= \mathcal{O}(Mk) \\ &= \mathcal{O}(M \sqrt Q) \kern{20pt}(\text{since }k = \mathcal{O}(\sqrt Q))\end{aligned}\]

(*) **Note**: Maximizing the expression can be formulated as the following linear program:

Maximize \(1\,d_2 + 2\,d_3 + \cdots + (k-1)\,d_k\), subject to \(d_i \ge 0\), and:

\[\begin{array}{rcl} d_1 + d_2 + \cdots + d_{k} &\le& 2M \\[3pt] d_1 - d_2 &\ge& 0 \\[3pt] d_2 - d_3 &\ge& 0 \\[5pt] & \vdots & \\[3pt] d_{k-1} - d_k &\ge& 0 \end{array}\]

Using LP methods, it can be verified that the max is attained when every \(d_i = \frac{2M}{k}\).

[See David Harmeyer's solution video here.](https://youtu.be/AbF6-TtkPLs)