Mobile

You want to buy a present for your little brother Ike, who only likes mobiles of a very particular shape.

A mobile is a hanging decoration made of several levels, usually suspended from the ceiling. It is built from horizontal rods. Each rod has a string tied to its left end and another to its right end, and each string holds either another rod or a single toy. A mobile is therefore a binary tree in which every rod has exactly two children (each child being another rod or a toy).

To please Ike, you must be able to rearrange the mobile so that both of the following conditions hold.

(i) All toys hang at the same level, or, if two toys hang at different levels, those levels differ by exactly 1. (The level of a toy is the number of horizontal rods on the path from that toy up to the ceiling.)

(ii) Whenever two toys hang at different levels, the toy on the left must be lower (that is, at a larger level) than the toy on the right.

You may swap the two ends of any single rod: untie the strings at its left and right ends and retie them on the opposite ends. This does not change the internal arrangement of the rods or toys hanging below; it simply exchanges the entire left subtree and right subtree of that rod.

For example, consider a mobile that satisfies condition (i) but not condition (ii): its leftmost toy sits higher (at a smaller level) than the toys to its right, which violates (ii). Swapping the two ends of the top rod (rod 1) exchanges the positions of rod 2 and rod 3, and then swapping the two ends of rod 2 exchanges the rod and the toy hanging below it; the result satisfies both conditions. Here two swaps are needed.

Decide whether the given mobile can be rearranged into a shape Ike likes and, if so, determine the minimum number of rod-end swaps required.

The first line contains an integer $n$, the number of rods in the mobile ($1 \le n \le 100000$). The rods are numbered from 1 to $n$.

Each of the next $n$ lines describes the connections of one rod; the $i$-th of these lines describes rod $i$ with two integers $l$ and $r$ separated by a single space. $l$ and $r$ describe what hangs from the left end and the right end of the rod, respectively. If a toy hangs there the value is $-1$; if another rod hangs there the value is that rod's number.

If another rod hangs below rod $i$, that rod's number is always greater than $i$. The rod at the very top of the mobile is always rod 1.

Print a single integer: the minimum number of rod-end swaps needed to rearrange the mobile into a shape Ike likes. If it is impossible, print $-1$.

Since every rod has exactly two children, the whole mobile is a binary tree, and swapping a rod's two ends is the same as exchanging its left and right subtrees. Because each rod's number is smaller than the numbers of its child rods, processing the rods from the highest number down to 1 lets you compute the answer bottom-up without recursion.