Valera has got n domino pieces in a row. Each piece consists of two halves — the upper one and the lower one. Each of the halves contains a number from 1 to 6. Valera loves even integers very much, so he wants the sum of the numbers on the upper halves and the sum of the numbers on the lower halves to be even.

To do that, Valera can rotate the dominoes by 180 degrees. After the rotation the upper and the lower halves swap places. This action takes one second. Help Valera find out the minimum time he must spend rotating dominoes to make his wish come true.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 100), denoting the number of dominoes Valera has. Next n lines contain two space-separated integers x_{i}, y_{i} (1 ≤ x_{i}, y_{i} ≤ 6). Number x_{i} is initially written on the upper half of the i-th domino, y_{i} is initially written on the lower half.


-----Output-----

Print a single number — the minimum required number of seconds. If Valera can't do the task in any time, print  - 1.


-----Examples-----
Input
2
4 2
6 4

Output
0

Input
1
2 3

Output
-1

Input
3
1 4
2 3
4 4

Output
1



-----Note-----

In the first test case the sum of the numbers on the upper halves equals 10 and the sum of the numbers on the lower halves equals 6. Both numbers are even, so Valera doesn't required to do anything.

In the second sample Valera has only one piece of domino. It is written 3 on the one of its halves, therefore one of the sums will always be odd.

In the third case Valera can rotate the first piece, and after that the sum on the upper halves will be equal to 10, and the sum on the lower halves will be equal to 8.

Difficulty: interview

Starter code:

Solutions:
N = int(input())
Check = False
Sum = 0
Sum_l, Sum_r = 0, 0
for i in range(N):
    x, y = list(map(int, input().split()))
    Sum_l += x
    Sum_r += y
    Sum += x + y
    if (x % 2 + y % 2) % 2:
        Check = True
if Sum % 2:
    print(-1)
elif Sum_l % 2:
    if not Check:
        print(-1)
    else:
        print(1)
elif Sum_l % 2 == 0:
    print(0)


from math import*
from random import*

n = int(input())
flag = False
A, B = 0, 0
for i in range(n):
    a, b = list(map(int, input().split()))
    if a % 2 != b % 2:
        flag = True
    A, B = A + a, B + b
if A % 2 == 0 and B % 2 == 0:
    print(0)
elif A % 2 == 1 and B % 2 == 1 and flag:
    print(1)
else:
    print(-1)

n = int(input())
a = 0
b = 0
ans = 0
for i in range (n):
    x, y = list(map(int, input().split()))
    if (x + y) % 2 == 1:
        ans = 1
    a += x
    b += y
if (a + b) % 2 == 1:
    print(-1)
elif a % 2 == b % 2 == 0:
    print(0)
elif ans == 0:
    print(-1)
else:
    print(1)


def main():
  n = int(input())
  
  sumtop = 0
  sumbottom = 0
  flippable = False
  for i in range(n):
    st = input()
    arr = st.split(" ")
    a = int(arr[0])
    b = int(arr[1])
    
    sumtop += a
    sumbottom += b
    
    if a%2 + b%2 == 1:
      flippable = True
  
  if sumtop%2 == 0 and sumbottom%2 == 0:
    print(0)
  elif sumtop%2 + sumbottom%2 == 1:
    print(-1)
  elif flippable:
    print(1)
  else:
    print(-1)
  
  
  
  
def __starting_point(): main()
__starting_point()

from functools import reduce

dominoes = [list([int(x) % 2 for x in input().split()]) for x in range(int(input()))]
temp1, temp2 = reduce(lambda a, x: (a + x[0]) % 2, dominoes, 0), reduce(lambda a, x: (a + x[1]) % 2, dominoes, 0)
if temp1 == temp2 == 0:
    print(0)
elif temp1 == temp2 == 1 and ([1, 0] in dominoes or [0, 1] in dominoes):
    print(1)
else:
    print(-1)


n = int(input())
A = [0 for q in range(n)]
B = [0 for q in range(n)]
for i in range(n):
    (A[i], B[i]) = list(map(int, input().split()))
s1 = sum(A)
s2 = sum(B)
if s1 % 2 == 0 and s2 % 2 == 0:
    print(0)
elif s1 % 2 == 1 and s2 % 2 == 1:
    p = 0
    for i in range(n):
        if A[i] % 2 != B[i] % 2:
            p = 1
            break
    if p == 1:
        print(1)
    else:
        print(-1)
else:
    print(-1)


import sys

n = int(input())
a, b = [], []
for i in range(n):
    x, y = list(map(int, input().split()))
    a.append(x)
    b.append(y)
if sum(a) % 2 == sum(b) % 2 == 0:
    print(0)
else:
    for i in range(n):
        a[i], b[i] = b[i], a[i]
        if sum(a) % 2 == sum(b) % 2 == 0:
            print(1)
            return
        a[i], b[i] = b[i], a[i]
    for i in range(n):
        for j in range(i + 1, n):
            a[i], b[i] = b[i], a[i]
            a[j], b[j] = b[j], a[j]
            if sum(a) % 2 == sum(b) % 2 == 0:
                prin(2)
                return
            a[i], b[i] = b[i], a[i]
            a[j], b[j] = b[j], a[j]
    print('-1')


n = int(input());
d = [];
for i in range (0, n):
    tmp = input().split();
    (x, y) = (tmp[0], tmp[1]);
    d.append((x, y));

xSum = 0;
ySum = 0;
for (x, y) in d :
    xSum += int(x);
    ySum += int(y);
if xSum % 2 == 0 and ySum % 2 == 0 :
    print((0));
elif (xSum + ySum) % 2 == 1 :
    print((-1));
else :
    result = False;
    for (x, y) in d :
        if (int(x) + int(y)) % 2 == 1 :
            result = True;
    if result == True :
        print((1));
    else :
        print((-1));




N = int(input())
A = [tuple(int(j) for j in input().split()) for i in range(N)]
S1, S2 = 0, 0

for a, b in A:
    S1 += a
    S2 += b

if S1 % 2 == 0 and S2 % 2 == 0:
    print(0)
    return

if (S1 % 2 == 0) ^ (S2 % 2 == 0):
    print(-1)
    return

for a, b in A:
    if (a % 2 == 0) ^ (b % 2 == 0):
        print(1)
        return

print(-1)


n=int(input())
a=[]
b=[]
s1=0
s2=0
k=0
for i in range(n):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)
    s1+=x
    s2+=y
if s1%2==0 and s2%2==0:
    print(0)
else:
    if (s1%2 ==0 and s2%2!=0) or(s1%2 !=0 and s2%2==0):
        print(-1)
    else:
        for i in range(n):
            if (a[i]%2==1 and b[i]%2==0) or (a[i]%2==0 and b[i]%2==1):
                print(1)
                break
            k+=1
if k==n :
    print(-1)

n = int(input())

sum_x = 0
sum_y = 0

odd_even = 0
odd_odd = 0
even_odd = 0
even_even = 0

for i in range(n):
    x, y = map(int, input().split())
    sum_x += x
    sum_y += y
    if x % 2 == 0 and y % 2 == 0:
        odd_odd += 1
    elif x % 2 == 0 and y % 2 == 1:
        odd_even += 1
    elif x % 2 == 1 and y % 2 == 0:
        even_odd += 1
    else:
        even_even += 1

if sum_x % 2 == 0 and sum_y % 2 == 0:
    print(0)
elif sum_x % 2 == 0 and sum_y % 2 == 1:
    print(-1)
elif sum_x % 2 == 1 and sum_y % 2 == 0:
    print(-1)
else: # even - even
    if even_odd >= 1 or odd_even >= 1:
        print(1)
    else:
        print(-1)

n = int(input())
dominos = [list(map(int, input().split())) for i in range(n)]
sum_1 = 0
sum_2 = 0
ind = False
for i in range(n):
    sum_1 += dominos[i][0] % 2
    sum_1 %= 2
    sum_2 += dominos[i][1] % 2
    sum_2 %= 2
    if dominos[i][1] % 2 != dominos[i][0] % 2:
        ind = True
if sum_1 == sum_2 == 1 and ind:
    print(1)
elif sum_1 == sum_2 == 0:
    print(0)
else:
    print(-1)

def __starting_point():
    N = int(input())
    su = 0
    sl = 0
    canF = False
    for i in range(N):
        arr = input().split(' ')
        a = int(arr[0])
        b = int(arr[1])
        if (a%2==0 and b%2==1) or (a%2==1 and b%2==0):
            canF = True
        su += a
        sl += b
    ans = -1
    if (su+sl)%2==1:
        ans = -1
    else:
        if su%2==0 and sl%2==0:
            ans = 0
        elif canF:
            ans = 1
        else:
            ans = -1
    print(ans)

__starting_point()

n = int(input())
count = -1
A = [0] * 3
for i in range(n):
    a, b = list(map(int, input().split()))
    if a % 2 == 1 and b % 2 == 1:
        A[0] += 1
    elif a % 2 == 1:
        A[1] += 1
    elif b % 2 == 1:
        A[2] += 1
if A[0] % 2 == 0 and (A[1] + A[2]) % 2 == 0:
    print(A[1] % 2)
elif (A[1] + A[2]) % 2 == 0 and (A[1] + A[2]) >= 2:
    if A[1] % 2 == A[2] % 2 == 1:
        print(0)
    else:
        print(1)
else:
    print(-1)
    


n = int(input())
pieces = []

sum_total = 0
sum_left = 0
for i in range(1, n + 1):
    keys = []
    piece = input().split()
    keys = [int(x) for x in piece]
    sum_total += sum(keys)
    pieces.append(keys)

canrotate = False
for i in range(n):
    sum_left += pieces[i][0]
    if pieces[i][0] % 2 != pieces[i][1] % 2:
        canrotate = True

if sum_total % 2 == 1:
    print(-1)
elif not canrotate and sum_left % 2 == 1:
    print(-1)
elif sum_left % 2 == 1:
    print(1)
else:
    print(0)


n = int(input())
A = [0 for q in range(n)]
B = [0 for q in range(n)]
for i in range(n):
    (A[i], B[i]) = list(map(int, input().split()))
s1 = sum(A)
s2 = sum(B)
if s1 % 2 == 0 and s2 % 2 == 0:
    print(0)
elif s1 % 2 == 1 and s2 % 2 == 1:
    p = 0
    for i in range(n):
        if A[i] % 2 != B[i] % 2:
            p = 1
            break
    if p == 1:
        print(1)
    else:
        print(-1)
else:
    print(-1)


'''
Created on Oct 10, 2013

@author: Anonymous
'''
n=int(input())
cnt=0
suma=sumb=0
for i in range(0,n):
    a,b=list(map(int,input().split()))
    if(a%2!=b%2):cnt+=1
    suma,sumb=suma+a,sumb+b
if(suma%2==0 and sumb%2==0):print(0)
elif(suma%2!=sumb%2):print(-1)
elif(cnt>0):print(1)
else: print(-1)
    


def __starting_point():
        n = int(input())
        topodds = 0
        bottomodds = 0
        flipabble = False
        for _ in range(n):
                top,bottom = list(map(int,input().split()))   
                if not flipabble and (top+bottom)%2 != 0:
                        flipabble=True
                topodds += 0 if (top % 2==0) else 1
                bottomodds += 0 if (bottom%2==0) else 1
        if (topodds+bottomodds)%2 != 0:
                print(-1)
        elif (topodds%2 != 0) or (bottomodds%2 != 0):
                print(1 if flipabble else -1)
        else:
                print(0)

__starting_point()

def readln(): return tuple(map(int, input().split()))

n, = readln()
a = b = c = 0
for _ in range(n):
    x, y = readln()
    a += x
    b += y
    c += (x % 2) ^ (y % 2)
if a % 2 == 0 and b % 2 == 0:
    print(0)
elif (a % 2) == (b % 2) and c:
    print(1)
else:
    print(-1)


n = int(input())
s1 = 0
s2 = 0
b = False
for i in range(n):
    x, y= map(int, input().split())
    if x % 2 != y % 2:
        b = True
    s1 += x % 2
    s2 += y % 2
if s1 % 2 == 0 and s2 % 2 == 0:
    print(0)
elif s1 % 2 == s2 % 2 and b:
    print(1)
else:
    print(-1)

n = int(input())
x = 0
y = 0
a = []
for i in range(n):
    a.append([int(x) for x in input().split()])
    x += a[-1][0]
    y += a[-1][1]

if x % 2 == 0 and y % 2 == 0:
    print(0)
elif x % 2 != 0 and y % 2 != 0:
    for i in a:
        if i[0] % 2 != i[1] % 2:
            print(1)
            return
    else:
        print(-1)
else:
    print(-1)

n = int(input())
A, B, C = 0, 0, 0
for i in range(n):
    a, b = map(int, input().split())
    A += a
    B += b
    if a % 2 != b % 2: C = 1
if A % 2 == 0 and B % 2 == 0: print(0)
elif A % 2 == 1 and B % 2 == 1 and C: print(1)
else: print(-1)

n = int(input())
a, b, c = 0, 0, 0
for i in range(n):
    x, y = map(int, input().split())
    a += x
    b += y
    if not c and (x + y) % 2: c = 1
a, b = a % 2, b % 2
print(a if a == b and (a == 0 or a == c) else -1)

import sys

class Reader:
	def __init__(self, file):
		self.tok, self.tok_length, self.tok_position = ([], 0, 0)
		self.lines, self.line_position = (file.readlines(), 0)

	def next_token(self):
		if self.tok_position < self.tok_length:
			self.tok_position += 1
			return self.tok[self.tok_position - 1]
		self.tok = self.lines[self.line_position].split()
		self.tok_length, self.tok_position = (len(self.tok), 0)
		self.line_position += 1
		return self.next_token()

	def next_line(self):
		self.tok, self.tok_length, self.tok_position = ([], 0, 0)
		self.line_position += 1
		return self.lines[self.line_position - 1]

def main():
	reader = Reader(sys.stdin)
	n = int(reader.next_token())
	ls = 0
	rs = 0
	cnt = 0
	for i in range(n):
		l = int(reader.next_token())
		r = int(reader.next_token())
		ls += l
		rs += r
		if (l % 2 != r % 2):
			cnt += 1
	if ((ls + rs) % 2 != 0):
		print(-1)
		return
	if (ls % 2 == 0) and (rs % 2 == 0):
		print(0)
		return
	if (cnt > 0):
		print(1)
		return
	print(-1)
		

def __starting_point():
	main()
__starting_point()

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split(' '))))
Summ1=Summ2=0
for i in range(n):
    Summ1+=a[i][0]
    Summ2+=a[i][1]
F = False

if Summ1//2 == Summ1/2 and Summ2//2 == Summ2/2:
    print(0)
    F = True

if Summ1//2 != Summ1/2 and Summ2//2 != Summ2/2 and n!=1:
    for i in range(n):
        if (a[i][1]//2!=a[i][1]/2 and a[i][0]//2==a[i][0]/2) or (a[i][0]//2!=a[i][0]/2 and a[i][1]//2==a[i][1]/2):
            print(1)
            F = True
            break
if F == False:
    print(-1)