题目描述

$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\}$ であるような状態に至ることです。これは可能でしょうか。可能であるなら、それに必要な最小の操作回数も求めてください。

输入格式

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

$N$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$

输出格式

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

题目大意

给定 $N$ 个集合 $S_1,S_2,\dots,S_N$。定义初始状态的每个 $i\in [1,n]$，有 $S_i=\{i\}$。

定义一次操作为，选定一个 $i\in [1,N-1]$，然后将 $S_i$ 与 $S_{i+1}$ 同时赋值为 $S_i \cup S_{i+1}$。形式化的，赋值 $U\gets S_i \cup S_{i+1}$，再赋值 $S_i \gets U$ 以及 $S_{i+1} \gets U$。

定义目标状态的每个 $i\in [1,n]$，有 $S_i=\{L_i, L_i+1,\dots, R_i-1, R_i\}$。

求出从初始状态到目标状态的最少操作次数，或者判断不可能达成。

• $1\le N \le 5\times 10^5$
• $1\le L_i \le R_i \le N$
• 输入均为整数

3
1 2
1 2
1 3

-1

4
1 3
1 4
1 4
2 4

4

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

以下のように操作を行うことで到達可能です。 - $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\} $ とする