题目描述

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

输入格式

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

$N$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_N$ $B_N$

输出格式

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

题目大意

现在有一个无向图，边数未知，每条边的长度都为1，有n个顶点，告诉你第1~n个顶点与第一个顶点和第二个顶点的距离，问所有满足条件的图中，边数最少为多少。(若没有满足条件的图，则输出-1)

4
0 1
1 0
1 1
2 1

4

3
0 1
1 0
2 2

-1

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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