有一副 $$$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$$$。
在第二个测试用例中,无法对牌组进行排序。