Problem:


Score : 1500 points

Problem Statement

There is an undirected connected graph with N vertices numbered 1 through N.
The lengths of all edges in this graph are 1.
It is known that for each i (1≦i≦N), the distance between vertex 1 and vertex i is A_i, and the distance between vertex 2 and vertex i is B_i.
Determine whether there exists such a graph.
If it exists, find the minimum possible number of edges in it.

Constraints

2≦N≦10^5

0≦A_i,B_i≦N-1

Input

The input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
:
A_N B_N

Output

If there exists a graph satisfying the conditions, print the minimum possible number of edges in such a graph. Otherwise, print -1.

Sample Input 1

4
0 1
1 0
1 1
2 1

Sample Output 1

4

The figure below shows two possible graphs. The graph on the right has fewer edges.

Sample Input 2

3
0 1
1 0
2 2

Sample Output 2

-1

Such a graph does not exist.



Sample input:
4
0 1
1 0
1 1
2 1


Sample output:
4

Submission status: Wrong Answer

Solution code:
n = input()
AB = [map(int, raw_input().split()) for i in xrange(n)]
if not AB[0][0] == AB[1][1] == 0:
    print -1
    exit(0)
if not AB[0][1] == AB[1][0]:
    print -1
    exit(0)
parent = range(n)
def root(x):
    if x == parent[x]:
        return x
    parent[x] = root(parent[x])
    return parent[x]
def unite(x, y):
    px = root(x)
    py = root(y)
    if px < py:
        parent[py] = px
    elif px > py:
        parent[px] = py
    return min(px, py)
d = AB[0][1]
used = [0]*n
chain = [0]*d
S = {}
Am = {}
Bm = {}
unite(0, 1)
used[0] = used[1] = 1
for i in xrange(n):
    ABi = AB[i]
    if ABi[0] + ABi[1] == d and 1 < ABi[0] < d and not chain[ABi[0]]:
        used[i] = 1
        chain[ABi[0]] = 1
        unite(0, i)
    S[tuple(ABi)] = i
    Am[ABi[0]] = i
    Bm[ABi[1]] = i
if sum(chain) != d-1:
    print -1
    exit(0)
ans = d
for i in xrange(n):
    if not used[i]:
        a, b = AB[i]
        if (a-1, b-1) in S:
            used[i] = 1
            unite(i, S[a-1, b-1])
            ans += 1
        else:
            if a-1 not in Am and b-1 not in Bm:
                print -1
                exit(0)
            unite(i, Am[a-1])
            unite(i, Bm[b-1])
            ans += 2
for i in xrange(n):
    root(i)
if sum(parent) == 0:
    print ans
else:
    print -1