配点 : $1500$ 点

問題文

$N$ 頂点の連結な無向グラフがあり、頂点には $1 \sim N$ の番号が付いています。 辺の長さはすべて $1$ です。 各 $i (1 \leq i \leq N)$ について、頂点 $1$ と頂点 $i$ の距離が $A_i$、頂点 $2$ と頂点 $i$ の距離が $B_i$ であることが分かっています。 このようなグラフが存在するかを判定してください。また、存在する場合は、辺の本数として考えられる最小値を求めてください。

制約

• $2 \leq N \leq 10^5$
• $0 \leq A_i,B_i \leq N-1$

入力

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

$N$

$A_1$ $B_1$

$A_2$ $B_2$

:

$A_N$ $B_N$

出力

条件を満たすグラフが存在する場合は辺の本数の最小値を、存在しない場合は -1 を出力せよ。

4
0 1
1 0
1 1
2 1

4

下図のような $2$ 種類のグラフが考えられますが、右のグラフの方が辺の本数が少ないです。

3
0 1
1 0
2 2

-1

このようなグラフは存在しません。