Subtask 1

For every node, run a DFS from that node to find its highest reachable node, and find the best answer out of all of those.

Time complexity: ~\mathcal{O}(N(N+M))~

Subtask 2

The graph can be treated as undirected in this subtask, so we just need to check the top ~2~ nodes (by label) in each component individually. One way to do this is to find each component using DFS.

Time complexity: ~\mathcal{O}(N+M)~

Subtask 3

We can use dynamic programming as the graph is a DAG. Let ~C_u~ be the list of nodes adjacent to node ~u~, our recurrence is ~dp[u] = \max(u, \max_{v \in C_u} dp[v])~.

Finally, the answer is now simply the lexicographically greatest pair ~(u, dp[u])~ such that ~u < dp[u]~.

Time complexity: ~\mathcal{O}(N+M)~

Subtask 4

We can rethink our strategy in subtask ~1~. Instead of applying our technique forwards by fixing node ~x~, we can instead search from every possible ~y~ on the reverse graph from the greatest to least label, marking nodes that we visit with the current label. If a node was already marked previously, we can show that the answer for that node and all nodes that are reachable from it is at least as good as our current answer and can thus skip it, so we only need to visit each node once.

Time complexity: ~\mathcal{O}(N+M)~