Domino

Description

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.

Sample Input

Input

2 4 2 6 4

Output

0

Input

1 2 3

Output

-1

Input

3 1 4 2 3 4 4

Output

1 题目大意：n为塔诺牌个数，输入n行，一行的两个数据代表一个塔诺牌的上下两个部分。要求塔诺牌的上（下）部分所有元素相加（其实就是每一列相加）的和为 偶数。如果不为偶数，可以调换一行中左右两个数据（即将塔诺牌上下翻转180度），调换一次用1秒。如果调换后也无法使两列都为偶数则输出-1，输入所用的时 间。 很简单，因为偶数相加和为偶数，所以只看奇数。 分三种情况： 塔诺牌　　　　　　　　　　　　上　　　　　　　　　　　　下　　　　　　　　输出 所有　　　　　　　　　　　　 奇数　　　　　　　　　　　偶数　　　　　　　　-1 奇数　　　　　　　　　　　　 偶数　　　　　　　　　　　奇数　　　　　　　　-1 相加　　　　　　　　　　　　 偶数　　　　　　　　　　　偶数　　　　　　　　0 和为　　　　　　　　　　　　 奇数　　　　　　　　　　　奇数　　　　　如果奇数旁（不论上下）有偶数则输出1，否则输出-1 一开始wrong answer了，错在这组测试数据： 3 2 3 1 1 2 3

1 #include
        
          2 #include
         
           3 using namespace std; 4  5 int main() 6 { 7     int upper[105],lower[105]; 8     int i, flag, n; 9     while (scanf("%d", &n) != EOF)10     {11         for (i = 0; i < n; i++)12             cin >> upper[i] >> lower[i];13         int sum1 = 0, sum2 = 0;14         for (i = 0 ;i < n; i++)15         {16             if (upper[i] % 2 != 0)17             {18                 sum1 += upper[i];19             }20             if (lower[i] % 2 != 0)21             {22                 sum2 += lower[i];23             }24         }25         flag = 0;26         if ((sum1 + sum2) % 2 != 0)27             cout<<"-1"<