MOBILE2 - Mobiles

题面翻译

你准备给弟弟Ike买一件礼物，但是，Ike挑选礼物的方式很特别：他只喜欢那些能按照他的特有方式排成有序的东西。

你准备给Ike买一个风铃。风铃是一种多层的装饰品，一般挂在天花板上。每个风铃都包含一些由竖直的线连起来的水平杆。每根杆的两端都有线连接，下面或者挂着另一根水平杆，或者挂着一个玩具。下面是一个风铃的例子：

为使你的弟弟满意，你需要选一个满足下面两个条件的风铃：

(1)所有的玩具都在同一层(也就是说，每个玩具到天花板之间的杆的个数是一样的)或至多相差一层。

(2)对于两个相差一层的玩具，左边的玩具比右边的玩具要更靠下一点。

风铃可以按照下面的规则重新排列：任选一根杆，将杆两端的线“交换”。也就是解开一根杆左右两端的线，然后将它们分别绑到杆的另一端。注意这个操作不会改变下面的杆上线的排列顺序。

由于你正在参加信息学奥林匹克的训练，所以你决定设计一个算法，判断能否通过重新排列，将一个给定的风铃变为Ike喜欢的样子。

考虑上面的例子，上图中的风铃满足条件(1)，却不满足条件(2)——最左边的那个玩具比它右边的要高。

但是，我们可以通过下面的步骤把这个风铃变成一个Ike喜欢的形式：

第一步，将杆1的左右两端交换，这使得杆2和杆3的位置互换，交换的结果如下图所示：

第二步，也是最后一步，将杆2的左右两端交换，这使得杆4到了左边，原来在左边的玩具到了右边，交换的结果如下图所示：

现在这个风铃就满足Ike的条件了。 你的任务是：给定一个风铃的描述，求出最少需要多少次交换才能使这个风铃满足Ike的条件(如果可能的话)。

输入的第一行包含一个整数n (1≤ n ≤ 1 00 000)，表示风铃中有多少根杆。

接下来的n行描述杆的连接信息。这部分的第i行包含两个由空格分隔的整数li和ri，描述杆i的左右两端悬挂的东西。如果挂的是一个玩具，则对应的值为-1，否则为挂在下面的杆的编号。

如果杆i下面挂有其它杆，则这些杆的编号将严格大于i。杆1位于风铃的顶部。

输出仅包含一个整数。表示最少需要多少次交换能使风铃满足Ike的条件。如果不可能满足，输出-1。

题目描述

You have been asked to buy a gift for your baby brother, Ike. However, you have noticed that Ike has a very particular taste in gifts. He only likes gifts that are configured in his particular style.

You have found a shop that sells mobiles. A mobile is a multi-layered decoration that is typically hung from the roof. Each mobile consists of a series of horizontal rods connected by vertical wires. Each rod has a wire hanging from both ends, which holds either another horizontal rod or a toy.

A sample mobile is shown below:

To satisfy your brother, you need to find a mobile that can be reconfigured so that:

(i) any two toys are either at the same level (that is, joined to the roof by the same number of rods), or di.er by only one level;

(ii) for any two toys that differ by one level, the toy to the left is further down than the toy to the right.

Mobiles can be reconfigured by performing swaps. A swap involves taking some rod, unhooking whatever is hanging beneath the left and right ends, and reattaching them at opposite ends (that is, the right and left ends respectively). This process does not modify the ordering of any rods or toys further down.

Since you are training for the Informatics Olympiad, you decide to write a program to test whether a given mobile can be reconfigured into a gift that Ike will like!

As an example, consider the mobile illustrated earlier. Ike will not like this mobile. Although it satisfies condition (i), it breaks condition (ii) — the toy at the leftmost end is at a higher level than the toys to its right.

However, the mobile can be reconfigured into a mobile that Ike will like. The following swaps are required:

1. First, the left and right ends of rod 1 are swapped. This exchanges the positions of rods 2 and 3, resulting in the following configuration:

2. Second, and finally, the left and right ends of rod 2 are swapped. This moves rod 4 to the left end of rod 2, and the toy to the right end of rod 2.

It can be seen that this final mobile satisfies Ike's requirements. All toys are at most one level apart, and the toys at a lower level are further to the left than the toys at a higher level.

Your task is, given a description of a mobile, to determine the smallest number of swaps required to reconfigure it so that Ike will like it (if this is possible). You may assume that the toys can never get in each other's way.

输入格式

Multiple test cases, the number of them will be given at the very first line.

For each test case:

The first line of input will contain the single integer n (1 <= n <= 100 000) representing the number of rods in the mobile. The rods are numbered 1, 2 , ..., n.

The following n lines will describe the connections for each rod. Specifically, the ith of these lines will describe rod i. Each of these lines will contain two integers l r separated by a single space, indicating what is hung beneath the left and right ends of the rod respectively. If a toy is hung beneath this rod, the corresponding integer l or r will be -1. Otherwise the integer l or r will be the number of a rod that is hung beneath this rod.

If there are any rods hanging beneath rod i, these rods will have numbers strictly greater than i. Rod 1 is the single rod at the top of the mobile.

输出格式

Output should consist of a single line containing a single integer, giving the smallest number of swaps required to reconfigure the mobile according to Ike's constraints. If this is not possible, you should output the integer -1.

样例 #1

样例输入 #1

1
6
2 3 
-1 4 
5 6 
-1 -1 
-1 -1 
-1 -1

样例输出 #1

2