← 返回题目列表

Codeforces · 1503/D

D. 翻转卡片

中文机器翻译题面 查看原题

有一副 $$$n$$$ 牌。第 $$$i$$$ 卡的正面有一个数字 $$$a_i$$$,背面有一个数字 $$$b_i$$$。 $$$1$$$ 到 $$$2n$$$ 之间的每个整数在卡片上只出现一次。

如果前面的值按升序排列并且后面的值按降序排列,则称一副牌已排序。也就是说,如果 $$$a_i< a_{i+1}$$$ 且 $$$b_i> b_{i+1}$$$ 对于所有 $$$1\le i<n$$$。

翻转一张牌 $$$i$$$ 意味着交换 $$$a_i$$$ 和 $$$b_i$$$ 的值。您必须翻转一些卡片子集(可能没有),然后将所有卡片按照您喜欢的任何顺序放置。为了对牌组进行排序,您必须翻转的最少卡片数量是多少?

输入

第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — 卡的数量。

接下来的 $$$n$$$ 行描述了卡片。这些行的第 $$$i$$$ 包含两个整数 $$$a_i, b_i$$$ ($$$1\le a_i, b_i\le 2n$$$)。 $$$1$$$ 和 $$$2n$$$ 之间的每个整数都只出现一次。

输出

如果无法对牌组进行排序,则输出“-1”。否则,输出对这副牌进行排序所需的最少翻转次数。

示例

输入 #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

注意

在第一个测试用例中,我们翻转卡片 $$$(1, 9)$$$ 和 $$$(2, 7)$$$。然后,该牌组的顺序为 $$$(3,10)、(5,8)、(6,4)、(7,2)、(9,1)$$$。它已排序,因为 $$$3<5<6<7<9$$$ 和 $$$10>8>4>2>1$$$。

在第二个测试用例中,无法对牌组进行排序。