文件读写

• 输入文件 trans.in
• 输出文件 trans.out

限制

• 1000ms
• 512MB

题目描述

程老师的展馆里有 $n$ 个展位，沿着一条直线排开，编号 $1$ 到 $n$。每个展位上都装有两台传送器，第 $i$ 个展位上的两台传送器分别标着数字 $a_i$ 与 $b_i$。

展馆的传送系统由一条全场统一的输送方向控制：任一时刻，输送方向要么是向前（朝编号增大的方向），要么是向后（朝编号减小的方向），初始时输送方向为向前。程老师站在展位 $i$ 上时，可以使用该展位上的任意一台传送器：若当前输送方向为向前，标着数字 $x$ 的传送器把他送到展位 $i + x$；若当前输送方向为向后，则送到展位 $i - x$。若目标展位的编号小于 $1$ 或者大于 $n$，这台传送器此时失灵，不能使用，它既不计入使用次数，也不会让输送方向发生变化。

每成功使用一台传送器之后，全场的输送方向立即翻转：向前变向后，向后变向前。

展位之间不能步行，程老师只能借助传送器移动。他从 $1$ 号展位出发，想要到达 $n$ 号展位。请你求出他最少需要使用传送器的次数；如果他无论如何都到不了 $n$ 号展位，输出 $-1$。

输入格式

输入第一行包含一个整数 $n$，表示展位的数量。

接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i, b_i$，表示第 $i$ 个展位上两台传送器所标的数字。

输出格式

输出一行一个整数，表示程老师最少需要使用传送器的次数；若无法到达 $n$ 号展位，输出 $-1$。

数据范围

特殊性质 A：对所有 $i$，$a_i = b_i$。

特殊性质 B：对所有 $i$，$a_i = 1$。

对于 $100\%$ 的数据，保证 $2 \leq n \leq 10^5$，$1 \leq a_i, b_i \leq n$。

5
3 1
1 1
1 2
1 1
1 1

3

3
1 1
1 1
1 1

-1

样例解释

样例 1：初始输送方向为向前。第 $1$ 次使用 $1$ 号展位上标着 $3$ 的传送器，从展位 $1$ 到展位 $4$，方向翻转为向后。第 $2$ 次在展位 $4$ 上向后传送，两台传送器都标着 $1$，落到展位 $3$ 后方向翻转为向前。第 $3$ 次在展位 $3$ 上向前传送：标着 $1$ 的那台指向展位 $4$，标着 $2$ 的那台指向展位 $5$，后者在范围内，使用后到达展位 $5$。两次以内到不了：第一次传送之后方向必为向后，而从展位 $1$ 向前最远只能到展位 $4$，第二次传送只可能落在展位 $1$ 或展位 $3$。

样例 2：$n = 3$，每个展位上的两台传送器都标着 $1$。第 $1$ 次从展位 $1$ 向前到展位 $2$，方向翻转为向后；第 $2$ 次从展位 $2$ 向后回到展位 $1$，方向翻转为向前。此后程老师所在的展位与当前的输送方向都与出发时相同，于是一直在展位 $1$ 与展位 $2$ 之间往返，到不了展位 $3$。