分数: 1500 点
问题陈述
有一个无向连通图 N 顶点编号 1 通过 N。 该图中所有边的长度为 1。 据了解,对于每一个 i (1≦i≦N),顶点之间的距离 1 和顶点 i is A_i,以及顶点之间的距离 2 和顶点 i is B_i。 判断是否存在这样的图。 如果存在,求其中最小可能的边数。
约束
- 2≦N≦10^5
- 0≦A_i,B_i≦N-1
输入
输入由标准输入按以下格式给出:
N A_1 B_1 A_2 B_2 : A_N B_N
输出
如果存在满足条件的图,则打印该图中可能的最小边数。否则,打印 -1.
示例输入 1
4 0 1 1 0 1 1 2 1
示例输出 1
4
下图显示了两个可能的图表。右边的图有较少的边。

示例输入 2
3 0 1 1 0 2 2
示例输出 2
-1
这样的图不存在。