Flip the Cards
Contest: Codeforces Round 712 (Div. 1)
Difficulty rating: 2600
Tags: 2-sat, constructive algorithms, data structures, greedy, sortings, two pointers

There is a deck of $$$n$$$ cards. The $$$i$$$-th card has a number $$$a_i$$$ on the front and a number $$$b_i$$$ on the back. Every integer between $$$1$$$ and $$$2n$$$ appears exactly once on the cards.

A deck is called sorted if the front values are in increasing order and the back values are in decreasing order. That is, if $$$a_i< a_{i+1}$$$ and $$$b_i> b_{i+1}$$$ for all $$$1\le i<n$$$.

To flip a card $$$i$$$ means swapping the values of $$$a_i$$$ and $$$b_i$$$. You must flip some subset of cards (possibly, none), then put all the cards in any order you like. What is the minimum number of cards you must flip in order to sort the deck?

Input format:
The first line contains a single integer $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — the number of cards.

The next $$$n$$$ lines describe the cards. The $$$i$$$-th of these lines contains two integers $$$a_i, b_i$$$ ($$$1\le a_i, b_i\le 2n$$$). Every integer between $$$1$$$ and $$$2n$$$ appears exactly once.

Output format:
If it is impossible to sort the deck, output "-1". Otherwise, output the minimum number of flips required to sort the deck.

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

Note:
In the first test case, we flip the cards $$$(1, 9)$$$ and $$$(2, 7)$$$. The deck is then ordered $$$(3,10), (5,8), (6,4), (7,2), (9,1)$$$. It is sorted because $$$3<5<6<7<9$$$ and $$$10>8>4>2>1$$$.

In the second test case, it is impossible to sort the deck.

Example input:
5
3 10
6 4
1 9
5 8
2 7

Example output:
2

Example input:
2
1 2
3 4

Example output:
-1

Editorial:
Suppose there is a sorted deck where the $$$i$$$-th card has $$$c_i$$$ on the front and $$$d_i$$$ on the back. That is, it looks like this:
$$$$$$ c_1< c_2< \cdots< c_n\\ d_1> d_2> \cdots> d_n $$$$$$
The values $$$1,\ldots, n$$$ must appear in some prefix of $$$c_i$$$ and some suffix of $$$d_i$$$. That is, they must all appear on distinct cards. So, if two values between $$$1$$$ and $$$n$$$ appear on the same card, we should report there is no solution.
Now, we know that every card in the input has a value in $$$[1,n]$$$ and a value in $$$[n+1,2n]$$$. Let $$$f(k)$$$ denote the number matched with the value $$$k$$$. Let's split the cards into two sets. Set $$$A$$$ will be the cards that will end with the smaller number on the front, and $$$B$$$ is the set of cards ending with the smaller number on the back. In each set, as the smaller numbers increase, the larger numbers decrease. Therefore, it must be possible to decompose $$$[f(1),\ldots,f(n)]$$$ into two decreasing subsequences, or there is no solution.
To decompose an array into two decreasing subsequences, there is a standard greedy approach. Also, note that any decomposition of $$$[f(1),\ldots,f(n)]$$$ into two decreasing sequences corresponds to a solution. In fact, we can put all the cards of one subsequence in $$$A$$$ and the rest in $$$B$$$, and it will create a sorted deck.
But how can we find the decomposition that corresponds to the minimum number of card flips? For every index $$$i$$$ such that $$$\min\limits_{j\le i} f(j)>\max\limits_{j>i}f(j)$$$, let's add a divider between $$$i$$$ and $$$i+1$$$. This splits the array $$$[f(1),\ldots, f(n)]$$$ into several segments. We can independently choose how to decompose each segment into two subsequences, and combining them is guaranteed to be a valid decomposition for the entire array. Also, there is a unique way to decompose each segment: the only choice is in which one we call the first subsequence. And so, we can independently choose for each segment the choice that requires the smallest number of flips.
Complexity is $$$O(n)$$$.