你需要为你的弟弟 Ike 买一份礼物。然而，你发现 Ike 对礼物的品味非常独特。他只喜欢按照他特定风格配置的礼物。

你找到了一家出售移动装饰品（mobile）的商店。移动装饰品是一种多层装饰，通常悬挂在屋顶上。每个移动装饰品由一系列通过垂直线连接的水平杆组成。每根杆的两端都挂着一根线，线下面要么是另一根水平杆，要么是一个玩具。

为了满足你弟弟的要求，你需要找到一个可以重新配置的移动装饰品，使得：

(i) 任意两个玩具要么处于同一层（即通过相同数量的杆连接到屋顶），要么层数相差仅为 1； (ii) 对于任意两个层数相差为 1 的玩具，位于左侧的玩具比位于右侧的玩具位置更低。

移动装饰品可以通过执行“交换”（swap）来重新配置。一次交换涉及取下某根杆，解开悬挂在左右两端的物体，并将它们重新挂在相反的一端（即分别挂在右端和左端）。这个过程不会改变任何更下方杆或玩具的顺序。

由于你正在为信息学奥林匹克竞赛进行训练，你决定编写一个程序来测试给定的移动装饰品是否可以被重新配置成 Ike 喜欢的样子！

例如，考虑前面展示的移动装饰品。Ike 不会喜欢这个装饰品。虽然它满足条件 (i)，但它违反了条件 (ii) —— 最左端的玩具比它右侧的玩具处于更高的层级。

然而，该装饰品可以被重新配置成 Ike 喜欢的样子。需要进行以下交换：

1. 首先，交换 1 号杆的左右两端。这交换了 2 号杆和 3 号杆的位置，得到以下配置：

1. 最后，交换 2 号杆的左右两端。这会将 4 号杆移动到 2 号杆的左端，并将玩具移动到 2 号杆的右端。

可以看出，最终的移动装饰品满足了 Ike 的要求。所有玩具的层数相差最多为 1，且层数较低的玩具位于层数较高的玩具的左侧。

你的任务是，给定一个移动装饰品的描述，确定将其重新配置为 Ike 喜欢的样子所需的最少交换次数（如果可能的话）。你可以假设玩具永远不会互相阻挡。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)，表示移动装饰品中杆的数量。杆的编号为 $1, 2, \dots, n$。

接下来的 $n$ 行描述每根杆的连接情况。具体来说，第 $i$ 行描述杆 $i$。每行包含两个整数 $l$ 和 $r$，中间用空格隔开，分别表示悬挂在杆的左端和右端的物体。如果悬挂的是玩具，则对应的整数 $l$ 或 $r$ 为 $-1$。否则，该整数为悬挂在该杆下方的杆的编号。

如果杆 $i$ 下方悬挂有其他杆，这些杆的编号将严格大于 $i$。1 号杆是位于移动装饰品顶部的单根杆。

输出格式

输出一行，包含一个整数，表示根据 Ike 的约束条件重新配置移动装饰品所需的最少交换次数。如果无法做到，则输出 $-1$。

样例

样例输入 1

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

样例输出 1

2

说明

上述样例输入描述了本题题目描述中的第一个插图。

子任务

对于每个输入场景，如果输出文件中写入了正确答案，则得分为 100%，否则为 0%。