1027F - Session in BSU
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≤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 cntec>cntvc then the answer for the day k is false. Otherwise the answer is true.

Overall complexity O(nlogn) 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!


int n;
vi m;
vpi v;

template<int SZ> struct DSU {
    int par[SZ], sz[SZ], co[SZ];
    vi tmp[SZ];

    DSU() {
        F0R(i,SZ) par[i] = i, sz[i] = 1;
    }

    int get(int x) { // path compression
        if (par[x] != x) par[x] = get(par[x]);
        return par[x];
    }

    bool unite(int x, int y) { // union-by-rank
        x = get(x), y = get(y);
        if (sz[x] < sz[y]) swap(x,y);
        co[x] ++;
        if (x == y) return 0;
        sz[x] += sz[y], co[x] += co[y], par[y] = x;
        return 1;
    }
};

int M(int x) {
    return lb(all(m),x)-m.begin();
}

DSU<MX> D;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    F0R(i,n) {
        int x,y; cin >> x >> y;
        m.pb(x), m.pb(y);
        v.pb({x,y});
    }
    sort(all(m)); m.erase(unique(all(m)),m.end());
    for (auto a: v) D.unite(M(a.f),M(a.s));
    F0R(i,sz(m)) D.tmp[D.get(i)].pb(m[i]);

    int cans = 0;
    F0R(i,sz(m)) if (D.get(i) == i) {
        if (D.co[i] > D.sz[i]) {
            cout << -1;
            exit(0);
        }
        sort(all(D.tmp[i]));
        if (D.co[i] == D.sz[i]) {
            cans = max(cans,D.tmp[i].back());
        } else {
            cans = max(cans,D.tmp[i][sz(D.tmp[i])-2]);
        }
    }
    cout << cans;
}