Problem Statement

Domino You have n domino pieces in a row. The upper and lower halves of piece i contain the non-negative integers x[i] and y[i] . You want both of these sums to be even: the sum of all values currently on the upper halves; the sum of all values currently on the lower halves. In one second, you may rotate one domino by 180 degrees. Its upper and lower values swap places. Find the minimum number of seconds needed. If it is impossible, print -1 . Input Format The first line contains an integer n , the number of dominoes. Each of the next n lines contains two space-separated integers x[i] and y[i] , where x[i] is initially on the upper half and y[i] is initially on the lower half of domino i . Output Format Print one integer: the minimum number of rotations, or -1 if no sequence of rotations makes both sums even. Constraints 1 ≤ n ≤ 100000 0 ≤ x[i], y[i] ≤ 10^9 Examples Example 1 Input: 2 4 2 6 4 Output: 0 Both sums are already even: the upper sum is 10 and the lower sum is 6 . Example 2 I