問題文


から までの番号が付いた 個のマスがあり、各 についてマス とマス は隣り合っています。最初、全てのマスの色は黒であり、Vil君はマス にいます。Vil君がマス にいるとき、行える操作は以下の 種類です。

  • 操作 : マス からマス までの色を白黒反転する。
  • 操作 : マス が白であるとき、隣り合う白いマスに移動する。

何回か操作を行ってマス に行くとき、操作 を行う回数の最小値を求めてください。マス に行くことが不可能な場合はそのことを報告してください。

制約


  • 入力はすべて整数

入力


N
L_1 R_1
L_2 R_2
...
L_N R_N

出力


マス に到達可能なら操作 を行う回数の最小値を、そうでなければ -1 を出力し、最後に改行してください。

入力例1

5
1 2
3 5
1 3
4 4
1 5
出力例1

2

マス で操作 を行う 操作 を行い、マス まで移動する マス で操作 を行う 操作 を(連続して)行い、マス まで移動する

この順序が最適で、操作 の回数の最小値は です。

入力例2

5
1 5
2 3
5 5
5 5
2 2
出力例2

1
入力例3

8
1 7
6 7
6 8
8 8
4 6
5 7
3 8
2 5
出力例3

2

Submit


Go (1.14)