Important: Make sure that 64-bit integers are used to store the edge weights and store ~f~ in all subtasks, or else you may get 0 points.

For subtask 1, the only possible paths are ~1 \to 3~ and ~1 \to 2 \to 3~. The shorter path is preferred. Find the number of people who can use the first path and the second path. Afterwards, it is possible to solve each query in constant time.

Note: There are test cases where 0 people can travel either of these paths, and Fail is the answer for every query.

Time Complexity: ~\mathcal{O}(Q)~

For subtask 2, perform a BFS search to get a valid path, then subtract the road durabilities by 1. Do this 300 times in total, and create a lookup table. Every query can be solved by using the lookup table.

Time Complexity: ~\mathcal{O}(\max(f) \times M + Q \times N)~

For subtask 3, perform a BFS search to get a valid path. Once a valid path is found, find the lowest road durability in the path, and subtract the road durabilities by this value. A lookup table can also be generated. This time, every query must binary search / lower_bound to find the correct index.

The number of possible paths is ~\mathcal{O}(M)~ (since a path removes at minimum, ~1~ edge), and every BFS search is ~\mathcal{O}(M)~. As a result, a naive implementation may fail subtasks 2 and 4. After doing constant optimization, this approach will perform approximately ~450~ million ~(\approx \frac 1 2 M^2)~ operations and can pass subtask 4. This was not the intended solution to the problem.

Note: In cases where no path exists between ~1~ and ~N~, the lookup table might be empty. In this case, every query should be answered with Fail.

Well-versed programmers may notice similarities with the Edmonds–Karp algorithm.

Time Complexity: ~\mathcal{O}(M^2 + Q \times (\log M + N))~

For subtask 4, the first observation is that the path length must be monotonically increasing. It is enough to find paths with ~2 \dots N~ nodes. For each possible path length, perform a BFS search and categorize nodes according to their distance from vertex ~1~. If a node with distance ~x~ goes to a node with distance ~x+1~, this edge must be included in a new graph. After all operations, this step is ~\mathcal{O}(M \times N)~.

After the new graph is generated, make sure to sort outgoing edges in the new graph. Note that stacks can be used to store the graph. After all operations, this step is ~\mathcal{O}(M \times N \log N)~.

Now, paths can easily be computed from the new graph. DFS is sufficient to grab a path. Make sure to get rid of edges that lead to nowhere. Notice that the runtime of a DFS is ~\mathcal{O}(N + \text{edges removed})~. After a new path is found, find the smallest edge durability and reduce all edges in this path. At least 1 edge will be deleted. To disconnect nodes ~1~ and ~N~, ~\mathcal{O}(M + \text{paths} \times N)~ operations go to DFS, and ~\mathcal{O}(\text{paths} \times N \log N)~ operations go to reducing edge durabilities.

Since there are ~\mathcal{O}(M)~ paths in total, the total number of operations is ~\mathcal{O}(M \times N \log N)~ to get and store all the paths in a lookup table. Every query can be solved by binary searching the lookup table.

Well-versed programmers may notice similarities with Dinic's algorithm.

Time Complexity: ~\mathcal{O}(M \times N \log N + Q \times (\log M + N))~