For the first subtask, we note that the graph is complete and that every edge has a cost of ~1~. That is, the time it takes to get from one node to any other node is ~1~. We then realize that at every node except for where an air body begins, a storm will form after ~1~ second. Extending this, if the two air bodies start at different nodes, any edge that connects to an air body cannot contain a storm (except the edge in the middle of the two bodies, and the answer is ~0.5)~, and every other edge will contain one at ~1~ second. In the case that the air bodies begin at the same node, all edges connecting to the initial storm will contain one at ~0~ seconds.

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

For the second subtask, we realize that the graph forms a tree and that the two air bodies immediately form a storm. Therefore, a storm reaches every single edge and node. For a given node, the time that the storm reaches there is equal to its distance from the start of the storm. We can find this distance by performing a BFS or DFS, since the graph is a tree. For a given edge, the time that the storm reaches there is the minimum time that it takes for the storm to reach a node that it connects to. Since there are many queries, we should perform one search to determine the time it takes to get to any node from the start.

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

For the third subtask, we realize that all queries will only ask for the time it takes for the storm to reach a node. Since the graph is no longer guaranteed to be a tree, we use a shortest path algorithm such as Dijkstra's Algorithm to compute the time it takes for an air body to reach a node. We should compute the distances for both of the air bodies (i.e., we need to run Dijkstra's twice).

To answer a query, we note that if one air body reaches the node earlier than the other, the former must certainly have blocked the latter from entering the node. Thus, the only case that remains is if both air bodies reach the node at the same time. In this case, a storm is formed. Therefore, it suffices to check if the times taken by the two air bodies to reach the query node are equal or not.

Since ~N~ is small, we can use the unoptimized version of Dijkstra.

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

For the final subtask, we must now use the priority queue version of Dijkstra since ~N~ is large, and also consider answering queries on edges.

Handling the edge query case can be tricky, as there are several cases we need to consider.

Suppose that for one node of an edge, one air body arrives earlier than the other. If that same air body arrives earlier in the other node, then no storm forms.

Now suppose that for one node of the edge, one air body arrives earlier than the other and both bodies arrive at the same time at the other node. There are two cases: only one air body occupies the edge and a storm is formed at that node, or the storm is present at that node and begins to travel down the edge. We deal with these two cases by comparing the time it would take for the air body to get to the other node and the actual shortest time. If these values are equal, then that means that the storm at the node is caused by the air body moving through the channel. Otherwise, the storm already existed and begins to travel through the edge.

Now suppose that for one node of the edge, one air body arrives earlier than the other and at the other node, the other air body arrives earlier. In this case, the storm will form at some point in the middle of the edge. We use some relatively simple arithmetic to calculate the exact time in which this occurs.

Finally, suppose that storms exist at both nodes, that is, the time it takes for one air body to reach either node is the same as the other body. In this case, we choose the minimum time it took for the storm to reach either node.

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