Session in BSU
Contest: Educational Codeforces Round 49 (Rated for Div. 2)
Difficulty rating: 2400
Tags: binary search, dfs and similar, dsu, graph matchings, graphs

Polycarp studies in Berland State University. Soon he will have to take his exam. He has to pass exactly $$$n$$$ exams.

For the each exam $$$i$$$ there are known two days: $$$a_i$$$ — day of the first opportunity to pass the exam, $$$b_i$$$ — day of the second opportunity to pass the exam ($$$a_i < b_i$$$). Polycarp can pass at most one exam during each day. For each exam Polycarp chooses by himself which day he will pass this exam. He has to pass all the $$$n$$$ exams.

Polycarp wants to pass all the exams as soon as possible. Print the minimum index of day by which Polycarp can pass all the $$$n$$$ exams, or print -1 if he cannot pass all the exams at all.

Input format:
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the number of exams.

The next $$$n$$$ lines contain two integers each: $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i < b_i \le 10^9$$$), where $$$a_i$$$ is the number of day of the first passing the $$$i$$$-th exam and $$$b_i$$$ is the number of day of the second passing the $$$i$$$-th exam.

Output format:
If Polycarp cannot pass all the $$$n$$$ exams, print -1. Otherwise print the minimum index of day by which Polycarp can do that.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
2
1 5
1 7

Example output:
5

Example input:
3
5 13
1 5
1 7

Example output:
7

Editorial:
This problem has many approaches (as Hall's theorem, Kuhn algorithm (???) and so on), I will explain one (or two) of them.
Let's find the answer using binary search. It is obvious that if we can pass all the exams in $$$k$$$ days we can also pass them in $$$k+1$$$ days.
For the fixed last day $$$k$$$ let's do the following thing: firstly, if there exists some exam with the day of the first opportunity to pass it greater than $$$k$$$, then the answer for the day $$$k$$$ is false.
Next, while there exist exams having only one possibility to pass them (because of the upper bound of the maximum possible day or constraints imposed by the other exams), we choose this day for this exam and continue (after choosing such day there can appear some new exams with the same property). Now there are no exams having only one day to pass them.
Let's take a look on the graph where vertices represent days and edges represent exams (the edge between some vertices $$$u$$$ and $$$v$$$ ($$$u < v$$$) exists iff there is an exam with the first day to pass it equal to $$$u$$$ and the second day to pass it equal to $$$v$$$). Let's remove all the exams for which we identified the answer. Now let's take a look on the connected components of this graph and analyze the problem which we have now. Our problem is to choose exactly one vertex incident to each edge of the connected component such that no vertex is chosen twice (and we have to do this for all the connected components we have).
Let $$$cntv$$$ be the number of vertices in the current connected component and $$$cnte$$$ be the number of edges in the current connected component. The answer for the connected component is true iff $$$cnte \le cntv$$$, for obvious reasons. There is very easy constructive method to see how we can do this. If $$$cnte < cntv$$$ then the current connected component is a tree. Let's remove some leaf of this tree and set it as the chosen vertex for the edge incident to this leaf (and remove this edge too). If $$$cnte = cntv$$$ then let's remove all leaves as in the algorithm for the tree. For the remaining cycle let's choose any edge and any vertex incident to it, set this vertex as the chosen to this edge and remove them. Now we have a chain. Chain is a tree, so let's apply the algorithm for the tree to this chain.
So, if for some connected component $$$c$$$ holds $$$cnte_c > cntv_c$$$ then the answer for the day $$$k$$$ is false. Otherwise the answer is true.
Overall complexity $$$O(n \log n)$$$ because of numbers compressing or using logarithmic data structures to maintain the graph.
Also there is another solution (which can be too slow, I don't know why it works). It is well-known fact that if we will apply Kuhn algorithm to the some bipartite graph in order of increasing indices of vertices of the left part, then the last vertex in the left part of this graph which is in the matching will be minimum possible. Oh, that's what we need! Let the left part of this graph consist of days and the right part consist of exams. The edge between some vertices $$$u$$$ from the left part and $$$v$$$ from the right part exists iff $$$u$$$ is one of two days to pass the exam $$$v$$$. Let's apply Kuhn algorithm to this graph, considering days in increasing order. The first day when matching becomes $$$n$$$ (all exams are in the matching) will be the answer. I don't know its complexity, really. Maybe it works too fast because of the special properties of the graph... If someone can explain in which time it works I will very happy!