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?


-----Input-----

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.


-----Output-----

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


-----Examples-----

Input
5
3 10
6 4
1 9
5 8
2 7
Output
2
Input
2
1 2
3 4
Output
-1
Input
3
1 2
3 6
4 5
Output
-1


-----Note-----

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.

Source: codeforces | Difficulty: VERY_HARD
Tags: Constructive algorithms

Strong connectivity

Sorting

Amortized analysis

Greedy algorithms

Data structures


Solutions:
import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LI1():
	return list(map(int1, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
inf = 10 ** 16
md = 10 ** 9 + 7
n = II()
rev = [0] * 2 * n
inc = [False] * 2 * n
ab = []
for _ in range(n):
	(a, b) = LI1()
	if a < b:
		ab.append((a, b, 0))
	else:
		ab.append((b, a, 1))
inc = sorted(ab, key=lambda x: -x[0])
dec = sorted(ab, key=lambda x: x[1])
al = []
bl = [2 * n]
ar = []
br = [-1]
ans = 0
fin = [False] * 2 * n
while inc and dec:
	c0 = c1 = 0
	(a, b, t) = inc.pop()
	if fin[a]:
		continue
	fin[a] = fin[b] = True
	al.append(a)
	bl.append(b)
	if t == 0:
		c0 += 1
	else:
		c1 += 1
	up = True
	while up:
		up = False
		while inc and inc[-1][0] < br[-1]:
			(a, b, t) = inc.pop()
			if fin[a]:
				continue
			fin[a] = fin[b] = True
			al.append(a)
			bl.append(b)
			if t == 0:
				c0 += 1
			else:
				c1 += 1
			up = True
		while dec and dec[-1][1] > bl[-1]:
			(a, b, t) = dec.pop()
			if fin[a]:
				continue
			fin[a] = fin[b] = True
			ar.append(b)
			br.append(a)
			if t == 0:
				c1 += 1
			else:
				c0 += 1
			up = True
	ans += min(c0, c1)

def ok():
	bb = br + bl[::-1]
	return bb == sorted(bb)
if ok():
	print(ans)
else:
	print(-1)


def sv():
	N = int(input())
	lf = [False] * N
	mt = [False] * N
	for n in range(N):
		(a, b) = map(int, input().split())
		sp = False
		if a > N:
			(a, b) = (b, a)
			sp = True
		if a > N or b <= N:
			return -1
		a -= 1
		b = 2 * N - b
		lf[a] = b
		if sp:
			mt[a] = True
	g0 = -1
	g1 = -1
	gm = -1
	cc = 0
	cs = 0
	ans = 0
	for n in range(N):
		cc += 1
		if lf[n] > g0 and (g0 >= g1 or lf[n] <= g1):
			g0 = lf[n]
			if mt[n]:
				cs += 1
		elif lf[n] > g1:
			g1 = lf[n]
			if not mt[n]:
				cs += 1
		else:
			return -1
		gm = max(gm, lf[n])
		if gm == n:
			ans += min(cs, cc - cs)
			cc = 0
			cs = 0
			g0 = n
			g1 = n
	return ans
print(sv())


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.buffer.readline
	N = int(input())
	AB = [-1] * (2 * N + 1)
	BA = [-1] * (2 * N + 1)
	for _ in range(N):
		(a, b) = map(int, input().split())
		AB[a] = b
		BA[b] = a
	seen = [0] * (2 * N + 1)
	small = 0
	large = 2 * N + 1
	top = []
	bottom = []
	ans = 0
	seen_sum = 0
	while True:
		cnt_all = 0
		cnt_flipped = 0
		small += 1
		cnt_all += 1
		if BA[small] != -1:
			cnt_flipped += 1
			L = BA[small]
		else:
			L = AB[small]
		top.append((small, L))
		seen[small] = 1
		seen[L] = 1
		small_new = small
		large_new = L
		seen_sum += 2
		while small != small_new or large_new != large:
			if large_new != large:
				for l in range(large - 1, large_new, -1):
					if seen[l]:
						continue
					cnt_all += 1
					if BA[l] != -1:
						cnt_flipped += 1
						s = BA[l]
					else:
						s = AB[l]
					bottom.append((l, s))
					seen[s] = 1
					seen[l] = 1
					seen_sum += 2
					small_new = max(small_new, s)
				large = large_new
			elif small_new != small:
				for s in range(small + 1, small_new):
					if seen[s]:
						continue
					cnt_all += 1
					if BA[s] != -1:
						cnt_flipped += 1
						l = BA[s]
					else:
						l = AB[s]
					top.append((s, l))
					seen[s] = 1
					seen[l] = 1
					large_new = min(large_new, l)
					seen_sum += 2
				small = small_new
			if seen_sum == 2 * N:
				break
		ans += min(cnt_flipped, cnt_all - cnt_flipped)
		if seen_sum == 2 * N:
			break
	bottom.reverse()
	top.extend(bottom)
	ok = 1
	for i in range(N - 1):
		if top[i][0] > top[i + 1][0] or top[i][1] < top[i + 1][1]:
			ok = 0
			break
	if ok:
		print(ans)
	else:
		print(-1)
main()


import sys, io, os
try:
	Z = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
except:
	Z = lambda : sys.stdin.readline().encode()

def sol(n, d, F):
	L = [[0] * (n + 2), [0] * (n + 2)]
	L[0][-1] = L[1][0] = 2 * n + 1
	q = [1]
	nq = []
	m = g = f = t = 0
	l = 1
	h = n + 1
	u = [0] * (2 * n + 1)
	u[1] = 1
	p = 1
	while l != h:
		if not q:
			t += min(f, g - f)
			f = g = m = 0
			while u[p]:
				p += 1
			q = [p]
			u[p] = 1
		else:
			while q:
				v = q.pop()
				g += 1
				f += F[v]
				u[d[v]] = 1
				if m:
					if L[0][h - 1] != 0:
						return -1
					L[0][h - 1] = v
					L[1][h - 1] = d[v]
					if v > L[0][h] or d[v] < L[1][h]:
						return -1
					for i in range(L[1][h] + 1, d[v]):
						if not u[i]:
							nq.append(i)
							u[i] = 1
					h -= 1
				else:
					if L[0][l] != 0:
						return -1
					L[0][l] = v
					L[1][l] = d[v]
					if v < L[0][l - 1] or d[v] > L[1][l - 1]:
						return -1
					for i in range(L[1][l - 1] - 1, d[v], -1):
						if not u[i]:
							nq.append(i)
							u[i] = 1
					l += 1
			m = 1 - m
			(q, nq) = (nq[::-1], [])
	for i in range(1, n + 2):
		if L[0][i] < L[0][i - 1] or L[1][i] > L[1][i - 1]:
			return -1
	t += min(f, g - f)
	return t
n = int(Z())
d = [0] * (2 * n + 1)
F = [0] * (2 * n + 1)
for _ in range(n):
	(a, b) = map(int, Z().split())
	d[a] = b
	d[b] = a
	F[a] = 1
print(sol(n, d, F))


number_of_cards = int(input())
opposite_side = {}
cards = set()
result = 0
top = []
bottom = []
highest_taken = 2 * number_of_cards + 1
lowest_taken = 0
for _ in range(number_of_cards):
	(front, back) = map(int, input().split())
	opposite_side[front] = back
	opposite_side[back] = front
	cards.add((front, back))

def end():
	print(-1)
	exit(0)
for i in range(1, 2 * number_of_cards + 1):
	if opposite_side[i] == -1:
		continue
	(a, b) = (i, opposite_side[i])
	(opposite_side[a], opposite_side[b]) = (-1, -1)
	top.append((a, b))
	counter = 1
	cost = 0 if (a, b) in cards else 1
	should_repeat = True
	candidate_max = b
	candidate_min = a
	while should_repeat:
		should_repeat = False
		while highest_taken > candidate_max:
			highest_taken -= 1
			if opposite_side[highest_taken] == -1:
				continue
			should_repeat = True
			(tmp_a, tmp_b) = (highest_taken, opposite_side[highest_taken])
			(opposite_side[tmp_a], opposite_side[tmp_b]) = (-1, -1)
			if (len(bottom) == 0 or (tmp_a < bottom[-1][0] and tmp_b > bottom[-1][1])) and (tmp_a > top[-1][0] and tmp_b < top[-1][1]):
				bottom.append((tmp_a, tmp_b))
				candidate_min = max(candidate_min, tmp_b)
				counter += 1
				if (tmp_a, tmp_b) not in cards:
					cost += 1
			else:
				end()
		while lowest_taken < candidate_min:
			lowest_taken += 1
			if opposite_side[lowest_taken] == -1:
				continue
			should_repeat = True
			(tmp_a, tmp_b) = (lowest_taken, opposite_side[lowest_taken])
			(opposite_side[tmp_a], opposite_side[tmp_b]) = (-1, -1)
			if (len(top) == 0 or (tmp_a > top[-1][0] and tmp_b < top[-1][1])) and (len(bottom) == 0 or (tmp_a < bottom[-1][0] and tmp_b > bottom[-1][1])):
				top.append((tmp_a, tmp_b))
				candidate_max = min(candidate_max, tmp_b)
				counter += 1
				if (tmp_a, tmp_b) not in cards:
					cost += 1
			else:
				end()
	result += min(cost, counter - cost)
print(result)


from sys import stdin

def solve():
	n = int(stdin.readline())
	dic = {}
	cards = set()
	for i in range(n):
		(a, b) = map(int, stdin.readline().split())
		a -= 1
		b -= 1
		dic[a] = b
		dic[b] = a
		cards.add((a, b))
	top = []
	bot = []
	used = [False] * (2 * n)
	left = 0
	right = 2 * n - 1
	left_target = 0
	right_target = 2 * n
	count = 0
	final_ans = 0
	try:
		while count != n:
			flag = True
			while left < left_target:
				flag = False
				while used[left]:
					left += 1
					if left == left_target:
						break
				else:
					(a, b) = (left, dic[left])
					top.append((a, b))
					used[a] = True
					used[b] = True
					right_target = min(right_target, b)
					count += 1
					left += 1
					if left == left_target:
						break
			if len(top) + len(bot) == n:
				continue
			while right > right_target:
				flag = False
				while used[right]:
					right -= 1
					if right == right_target:
						break
				else:
					(a, b) = (right, dic[right])
					bot.append((a, b))
					used[a] = True
					used[b] = True
					left_target = max(left_target, b)
					count += 1
					right -= 1
					if right == right_target:
						break
			if flag:
				srt = top + bot[::-1]
				for i in range(len(srt) - 1):
					if not (srt[i][0] < srt[i + 1][0] and srt[i][1] > srt[i + 1][1]):
						return -1
				else:
					ans = 0
					for c in top + bot:
						if c in cards:
							ans += 1
					final_ans += min(ans, len(top) + len(bot) - ans)
				left_target += 1
				right_target -= 1
				top = []
				bot = []
		if count == n:
			srt = top + bot[::-1]
			for i in range(len(srt) - 1):
				if not (srt[i][0] < srt[i + 1][0] and srt[i][1] > srt[i + 1][1]):
					return -1
			else:
				ans = 0
				for c in top + bot:
					if c in cards:
						ans += 1
				final_ans += min(ans, len(top) + len(bot) - ans)
				return final_ans
	except:
		return -1
print(solve())


import sys
input = lambda : sys.stdin.readline().rstrip()
from collections import deque
N = int(input())
X = [0] * (2 * N)
for i in range(N):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	X[a] = (0, b)
	X[b] = (1, a)
(l, r) = (0, 2 * N - 1)
done = [0] * (2 * N)
Q = deque([])
R = deque([])
mi = 0
ma = 2 * N - 1
ans = 0
while l <= r:
	while done[l]:
		l += 1
		if l > r:
			break
	if l > r:
		break
	x = l
	done[x] = 1
	l += 1
	(p, y) = X[x]
	done[y] = 1
	c = 1
	s = p
	while 1:
		while r > y:
			if not done[r]:
				R.append(r)
				done[r] = 1
			r -= 1
		if not R:
			break
		while R:
			x = R.popleft()
			(p, y) = X[x]
			if done[y]:
				print(-1)
				exit()
			done[y] = 1
			if y < mi:
				print(-1)
				exit()
			c += 1
			s += p
			mi = y
		while l < mi:
			if not done[l]:
				Q.append(l)
				done[l] = 1
			l += 1
		if not Q:
			break
		while Q:
			x = Q.popleft()
			(p, y) = X[x]
			if done[y]:
				print(-1)
				exit()
			done[y] = 1
			if y > ma:
				print(-1)
				exit()
			c += 1
			s += p
			ma = y
	ans += min(s, c - s)
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
front = [-1] * n
back = [-1] * n
rev = [-1] * (2 * n)
used = [False] * n
opp = [-1] * (2 * n)
for c in range(n):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	front[c] = a
	back[c] = b
	rev[a] = c
	rev[b] = c
	opp[a] = b
	opp[b] = a
left = -1
right = 2 * n
out = 0
works = True
while right - left > 1:
	s_l = left + 1
	s_r = right
	curr = 0
	curr_f = 0
	while (s_l > left or s_r < right) and right - left > 1:
		if s_l > left:
			left += 1
			card = rev[left]
			if not used[card]:
				used[card] = True
				curr += 1
				if front[card] == left:
					curr_f += 1
				if opp[left] < s_r:
					s_r = opp[left]
				else:
					works = False
		elif s_r < right:
			right -= 1
			card = rev[right]
			if not used[card]:
				used[card] = True
				curr += 1
				if front[card] == right:
					curr_f += 1
				if opp[right] > s_l:
					s_l = opp[right]
				else:
					works = False
	if s_l > s_r:
		works = False
	if not works:
		break
	out += min(curr_f, curr - curr_f)
if works:
	print(out)
else:
	print(-1)