UVa 11106 - Rectilinear Polygon

// UVa 11106 - Rectilinear Polygon

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

#define integer signed long long int

struct point {
	integer x, y;
	int z;
};

point p[100000];
int lnk[100000][2];

bool byx(point a, point b) {
	return a.x < b.x || (a.x == b.x && a.y < b.y);
}

bool byy(point a, point b) {
	return a.y < b.y || (a.y == b.y && a.x < b.x);
}

int main() {
	int tt;
	scanf("%d", &tt);
	for (int t = 0; t < tt; t++) {
		int n;
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			scanf("%lld%lld", &p[i].x, &p[i].y);
			p[i].z = i;
		}

		integer sol = 0;

		sort(p, p + n, byx);
		int c = 1;
		for (int i = 1; i < n; i++) {
			if (p[i].x == p[i - 1].x)
				c++;
			else {
				if (c & 1) {
					sol = -1;
					break;
				}
				c = 1;
			}
			if ((c & 1) == 0) {
				sol += p[i].y - p[i - 1].y;
				lnk[p[i].z][0] = p[i - 1].z;
				lnk[p[i - 1].z][0] = p[i].z;
			}
		}
		if (c & 1)
			sol = -1;
		if (sol != -1) {

			sort(p, p + n, byy);
			c = 1;
			for (int i = 1; i < n; i++) {
				if (p[i].y == p[i - 1].y)
					c++;
				else {
					if (c & 1) {
						sol = -1;
						break;
					}
					c = 1;
				}
				if ((c & 1) == 0) {
					sol += p[i].x - p[i - 1].x;
					lnk[p[i].z][1] = p[i - 1].z;
					lnk[p[i - 1].z][1] = p[i].z;
				}
			}
			if (c & 1)
				sol = -1;
		}

		//
		int a = 0, d = 0;
		int m = 1;

		while (true) {
			d = (d + 1) & 1;
			int b = lnk[a][d];
			if (b == 0)
				break;
			a = b;
			m++;
		}
		if (m < n)
			sol = -1;

		cout << sol << endl;

	}
	return 0;
}