Flip the Cards

题意翻译

你有 $n$ 张牌（编号为 $1$ 到 $n$），第 $i$ 张牌的正面有整数 $a_i$，背面有整数 $b_i$。所有 $1$ 到 $2\times n$ 的整数都在这 $n$ 张牌里出现过正好一次。 我们认为这 $n$ 张牌是“排好序”的仅当对于任意整数 $i\in[1,n)$ 有 $a_i<a_{i+1},b_i>b_{i+1}$。 你可以进行进行下面的操作任意次： - 选择一张牌 $i$ 并把它翻过来，即交换 $a_i,b_i$。 - 重新排序这 $n$ 张牌，顺序随意。 求如果要使这 $n$ 张牌变成“排好序”的，你最少需要翻几次牌，或告知无解。 $1\leq n\leq2\times10^5;1\leq a_i,b_i\leq2\times10^5;$

题目描述

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?

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

5
3 10
6 4
1 9
5 8
2 7

输出样例 #1

2

输入样例 #2

2
1 2
3 4

输出样例 #2

-1

输入样例 #3

3
1 2
3 6
4 5

输出样例 #3

-1

说明

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.

题意翻译

你有 $n$ 张牌（编号为 $1$ 到 $n$），第 $i$ 张牌的正面有整数 $a_i$，背面有整数 $b_i$。所有 $1$ 到 $2\times n$ 的整数都在这 $n$ 张牌里出现过正好一次。 我们认为这 $n$ 张牌是“排好序”的仅当对于任意整数 $i\in[1,n)$ 有 $a_i<a_{i+1},b_i>b_{i+1}$。 你可以进行进行下面的操作任意次： - 选择一张牌 $i$ 并把它翻过来，即交换 $a_i,b_i$。 - 重新排序这 $n$ 张牌，顺序随意。 求如果要使这 $n$ 张牌变成“排好序”的，你最少需要翻几次牌，或告知无解。 $1\leq n\leq2\times10^5;1\leq a_i,b_i\leq2\times10^5;$