时间限制： 1.0 秒

空间限制： 256 MB

题目描述

八皇后问题是一个以国际象棋为背景的问题：如何能够在 $8 \times 8$ 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

八皇后问题可以推广为更一般的 $n$ 皇后摆放问题：这时棋盘的大小变为 $n \times n$，而皇后个数也变成 $n$。

现在给你 $n$ 个皇后的位置座标，问总共有多少对皇后互相冲突。

输入格式

从标准输入读入数据。

第一行一个整数 $n$，表示有 $n$ 个皇后。

接下来 $n$ 行，每行两个整数 $x , y~(1\le x,y\le n)$，中间用空格分开，表示 $n$ 个皇后的坐标。

数据保证不会有两个皇后在同一个地方。

输出格式

输出到标准输出。

输出一个整数，表示有多少对皇后互相冲突。

3
1 1
1 2
1 3

3

2
1 1
2 2

1

4
1 3
2 1
3 4
4 2

0

子任务

数据规模约定：

对于 $60 \%$ 的数据，$1 \leq n \leq 100$。

对于 $100 \%$ 的数据，$1 \leq n \leq 10^{5}$。