Обозначим размер максимального паросочетания в графе $$$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
Название |
---|