← 返回题目列表

AtCoder · codefestival_2016_ex_a

A. 距离对

中文机器翻译题面 查看原题

分数: 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

这样的图不存在。