Rectilinear Polygon

Time limit1sMemory limit128 MB

Summary

Given n integer points, decide whether they can be the vertices of a simple rectilinear polygon, and if so output its perimeter, else -1.

Level: Medium7 of 10
Topics: Geometry, Sorting, Implementation
Solved: No attempts yet

Problem

You are given $n$ points with integer coordinates in the plane. Determine whether it is possible to build a simple rectilinear polygon whose vertices are exactly these points.

A rectilinear polygon satisfies all of the following:

It has at least $4$ vertices.
Every edge is either horizontal or vertical.
Each vertex is an endpoint of exactly one horizontal edge and exactly one vertical edge.
It is simple: no two edges cross, other than adjacent edges meeting at a shared endpoint, and the polygon has no holes.

Every given point must be used as a vertex. If such a polygon exists, output its perimeter (the sum of the lengths of all edges); otherwise output $-1$ .

Input

The first line contains an integer, the number of test cases.

Each test case begins with an integer $n$ ( $4 \le n \le 100000$ ), the number of points, followed by $n$ pairs of integers giving the $x$ and $y$ coordinates of the points.

Output

For each test case output a single line. If a valid rectilinear polygon through the given points exists, output its perimeter as an integer; otherwise output $-1$ .

Examples3

Example 1
Input
```
1
8
1 2
1 0
2 1
2 2
3 2
3 1
4 0
4 2
```
Expected output
```
12
```
Example 2
Input
```
1
4
0 0
2 0
2 3
0 3
```
Expected output
```
10
```
Example 3
Input
```
1
4
0 0
1 0
1 1
0 1
```
Expected output
```
4
```