E. Сумма паросочетаний
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Обозначим размер максимального паросочетания в графе $$$G$$$ как $$$\mathit{MM}(G)$$$.

Задан двудольный граф. Вершины первой доли пронумерованы от $$$1$$$ до $$$n$$$. Вершины второй доли пронумерованы от $$$n+1$$$ до $$$2n$$$. Степень каждой вершины равна $$$2$$$.

Для четверки целых чисел $$$(l, r, L, R)$$$, где $$$1 \le l \le r \le n$$$ и $$$n+1 \le L \le R \le 2n$$$, определим $$$G'(l, r, L, R)$$$ как граф, который состоит из всех вершин заданного графа, которые находятся либо в отрезке $$$[l, r]$$$, либо в отрезке $$$[L, R]$$$, и всех ребер заданного графа таких, что вершины их концов принадлежат одному из этих отрезков. Другими словами, чтобы получить граф $$$G'(l, r, L, R)$$$ из изначального графа, надо удалить все вершины $$$i$$$ такие, что $$$i \notin [l, r]$$$ и $$$i \notin [L, R]$$$, и все инцидентные им ребра.

Посчитайте сумму $$$\mathit{MM}(G(l, r, L, R))$$$ по всем наборам целых чисел $$$(l, r, L, R)$$$ таких, что $$$1 \le l \le r \le n$$$ and $$$n+1 \le L \le R \le 2n$$$.

Входные данные

В первой строке записано одно целое число $$$n$$$ ($$$2 \le n \le 1500$$$) — количество вершин в каждой доле.

Затем следует $$$2n$$$ строке, в каждой записано ребро графа. В $$$i$$$-й строке записано два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i \le n$$$; $$$n + 1 \le y_i \le 2n$$$) — концы $$$i$$$-го ребра.

В графе нет кратных ребер, и у каждой вершины ровно два инцидентных ребра.

Выходные данные

Выведите одно целое число — сумму $$$\mathit{MM}(G(l, r, L, R))$$$ по всем наборам целых чисел $$$(l, r, L, R)$$$, у которых $$$1 \le l \le r \le n$$$ и $$$n+1 \le L \le R \le 2n$$$.

Пример
Входные данные
5
4 6
4 9
2 6
3 9
1 8
5 10
2 7
3 7
1 10
5 8
Выходные данные
314