Codeforces Round 712 (Div. 1) |
---|
Закончено |
Есть колода из $$$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». В противном случае выведите минимальное количество карт, которые необходимо перевернуть, чтобы отсортировать колоду.
5 3 10 6 4 1 9 5 8 2 7
2
2 1 2 3 4
-1
3 1 2 3 6 4 5
-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$$$.
Во втором примере отсортировать колоду невозможно.
Название |
---|