你准备给弟弟Ike买一件礼物，但是，Ike挑选礼物的方式很特别：他只喜欢那些能按照他的特有方式排成有序的东西。
你准备给Ike买一个风铃。风铃是一种多层的装饰品，一般挂在天花板上。每个风铃都包含一些由竖直的线连起来的水平杆。每根杆的两端都有线连接，下面或者挂着另一根水平杆，或者挂着一个玩具。下面是一个风铃的例子：
为使你的弟弟满意，你需要选一个满足下面两个条件的风铃：
(1) 所有的玩具都在同一层(也就是说，每个玩具到天花板之间的杆的个数是一样的)或至多相差一层。
(2) 对于两个相差一层的玩具，左边的玩具比右边的玩具要更靠下一点。
风铃可以按照下面的规则重新排列：任选一根杆，将杆两端的线“交换”。也就是解开一根杆左右两端的线，然后将它们分别绑到杆的另一端。注意这个操作不会改变下面的杆上线的排列顺序。
由于你正在参加信息学奥林匹克的训练，所以你决定设计一个算法，判断能否通过重新排列，将一个给定的风铃变为Ike喜欢的样子。
考虑上面的例子，上图中的风铃满足条件(1)，却不满足条件(2)——最左边的那个玩具比它右边的要高。
但是，我们可以通过下面的步骤把这个风铃变成一个Ike喜欢的形式：
1. 第一步，将杆1的左右两端交换，这使得杆2和杆3的位置互换，交换的结果如下图所示：
2. 第二步，也是最后一步，将杆2的左右两端交换，这使得杆4到了左边，原来在左边的玩具到了右边，交换的结果如下图所示：
现在这个风铃就满足Ike的条件了。
你的任务是：给定一个风铃的描述，求出最少需要多少次交换才能使这个风铃满足Ike的条件(如果可能的话)。
输入的第一行包含一个整数n (1≤ n ≤ 1 00 000)，表示风铃中有多少根杆。
接下来的n行描述杆的连接信息。这部分的第i行包含两个由空格分隔的整数li和ri，描述杆i的左右两端悬挂的东西。如果挂的是一个玩具，则对应的值为-1，否则为挂在下面的杆的编号。
如果杆i下面挂有其它杆，则这些杆的编号将严格大于i。杆1位于风铃的顶部。
6 2 3 -1 4 5 6 -1 -1 -1 -1 -1 -1
2
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1K
公開 測資點#9 (5%): 1.0s , <1K
公開 測資點#10 (5%): 1.0s , <1K
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1K
公開 測資點#13 (5%): 1.0s , <1K
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
上面的样例输入给出了前面描述的示例情形。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||