配点 : $1500$ 点

問題文

$N$ 個の集合 $S_1, S_2, \ldots, S_N$ があります。はじめ、$1$ から $N$ までの各 $i$ について、集合 $S_i$ は整数 $i$ のみを含みます（すなわち、$S_i = \{i\}$ です）。

あなたは、次の操作を行うことができます。

• $1 \le i \le N-1$ であるような $i$ を任意に選び、$U = S_i \cup S_{i+1}$（$S_i$ と $S_{i+1}$ の和集合）とする。 そして、$S_i, S_{i+1}$ をともに $U$ で置き換える。

あなたの目標は、有限回の操作を行い（$0$ 回でもよい）、$1$ から $N$ までの全ての $i$ について $S_i = \{L_i, L_i+1, \ldots, R_i-1, R_i\}$ であるような状態に至ることです。これは可能でしょうか。可能であるなら、それに必要な最小の操作回数も求めてください。

制約

• $1 \le N \le 5\cdot 10^5$
• $1 \le L_i \le R_i \le N$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$L_1$ $R_1$

$L_2$ $R_2$

$\vdots$

$L_N$ $R_N$

出力

目標状態が到達可能なら、到達に必要な最小の操作回数を出力せよ。そうでなければ、-1 を出力せよ。

3
1 2
1 2
1 3

-1

目標状態が到達不能であることを証明できます。

4
1 3
1 4
1 4
2 4

4

以下のように操作を行うことで到達可能です。

• $i = 2$ を選び、$S_1 = \{1\}, S_2 = \{2, 3\}, S_3 = \{2, 3\}, S_4 = \{4\}$ とする
• $i = 1$ を選び、$S_1 = \{1, 2, 3\}, S_2 = \{1, 2, 3\}, S_3 = \{2, 3\}, S_4 = \{4\}$ とする
• $i = 3$ を選び、$S_1 = \{1, 2, 3\}, S_2 = \{1, 2, 3\}, S_3 = \{2, 3, 4\}, S_4 = \{2, 3, 4\}$ とする
• $i = 2$ を選び、$S_1 = \{1, 2, 3\}, S_2 = \{1, 2, 3, 4\}, S_3 = \{1, 2, 3, 4\}, S_4 = \{2, 3, 4\}$ とする