Есть колода из \(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\). Вы должны перевернуть некоторое подмножество карт (возможно, ни одной), а затем разместить эти карты в каком-то порядке. Какое минимальное количество карт вы должны перевернуть, чтобы отсортировать колоду?
Выходные данные
Если отсортировать колоду невозможно, выведите «-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\).
Во втором примере отсортировать колоду невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 10
6 4
1 9
5 8
2 7
|
2
|
|
2
|
2
1 2
3 4
|
-1
|
|
3
|
3
1 2
3 6
4 5
|
-1
|