First, let's introduce the notion of Strongly Connected Components (SCC). In a directed graph, a subset of nodes is strongly connected if there exists a path between any two nodes of the subset. Each directed graph can be decomposed into strongly connected components, such that the number of these components is as small as possible. There are various algorithms which do this and we will mention them later. For now, we can notice that the size of the maximal set from the problem is actually just the number of SCCs (we take one node from each SCC and it is obvious that this is maximal). So the problem is actually asking us to orient the edges in such a way as to minimize the number of SCCs in the graph.

The first subtask can be solved by trying all the combinations of flight routes, decomposing the graph into SCCs and counting them. In this case, the SCCs could be found naively. For example, for each city, we can find all the cities reachable from it and then for each pair of cities if both are reachable from each other then they belong to the same component.

For the remaining subtasks, one needs to notice that each SCC will consist of two intervals of consecutive nodes, one from each river. The proof of this claim is simple and is left as an exercise for the reader. Let's look at the flight routes and sort them from left to right on both rivers separately. Clearly, each city on the first river to the left of the first flight route is part of its own SCC because it's not possible to come back to it. Therefore, let's look at the first node on the first river which has a flight route and the first node on the second river which has a flight route. If these two nodes are connected by a flight route, and if they are not connected to any other flight routes, then this flight route is useless. Indeed, whichever orientation we choose for it, it's not possible to return to the city from which the route starts. Now we assume that there exists a route connecting one of the leftmost cities to some city to the right of the leftmost city on the other river. Without loss of generality assume this route connects the leftmost city of the first river with a city from the second river. If we orient this route so that it goes from the second river to the first, and if we orient the route connecting the leftmost node from the second river so that it's going from the first river to the second river, then we obtain an SCC consisting of the intervals determined by the leftmost nodes and the other ends of the routes (Here we should notice an edge case. We did not demand that the route starting from the leftmost node of the second river connects to some node to the right of the leftmost node on the first river. In fact, it's possible that this route connects precisely the two leftmost nodes. This is not a problem, as the interval on the first river will then simply be one node). Let's now look at some other flight route where at least one of its nodes is part of the current SCC. Without loss of generality assume it is a city from the first river. If the other end of the route is also a part of the current SCC, then this route doesn't affect anything because the two cities are already connected both ways. If the other city is not a part of the current SCC, then it is clearly to the right of the current interval on the second river (if it were to the left, we would have a contradiction with choosing the leftmost cities). It is easily seen that if we orient this flight route so that it goes from the second river to the first river, the SCC interval on the second river will expand to the right. Now we repeat this procedure, that is we expand the intervals of the current SCC until there is no more flight route for which at least one end is in the current SCC. Once no such routes are left, we cannot expand the current SCC and it has the maximal possible size. Now we can repeat this algorithm by ignoring the nodes of this SCC and looking for the leftmost nodes on each river again.

After we determine the orientations of the routes, what remains is to count the number of SCCs and print it. This is possible with a naive implementation described in the first subtask. For the whole solution, one could implement one of the well-known algorithms for finding SCCs in linear time complexity such as Tarjan's or Kosaraju's. Note that it is not actually required to know any of these algorithms to solve the problem. Instead, we can easily see that if there were no routes, the answer would be ~a+b~, and as we connect the nodes into SCCs, we keep track of how many nodes have been added and reduce the answer by that much.