CF1651E.Sum of Matchings

Let's denote the size of the maximum matching in a graph $G$ as $\mathit{MM}(G)$.

You are given a bipartite graph. The vertices of the first part are numbered from $1$ to $n$, the vertices of the second part are numbered from $n+1$ to $2n$. Each vertex's degree is $2$.

For a tuple of four integers $(l, r, L, R)$, where $1 \le l \le r \le n$ and $n+1 \le L \le R \le 2n$, let's define $G'(l, r, L, R)$ as the graph which consists of all vertices of the given graph that are included in the segment $[l, r]$ or in the segment $[L, R]$, and all edges of the given graph such that each of their endpoints belongs to one of these segments. In other words, to obtain $G'(l, r, L, R)$ from the original graph, you have to remove all vertices $i$ such that $i \notin [l, r]$ and $i \notin [L, R]$, and all edges incident to these vertices.

Calculate the sum of $\mathit{MM}(G(l, r, L, R))$ over all tuples of integers $(l, r, L, R)$ having $1 \le l \le r \le n$ and $n+1 \le L \le R \le 2n$.

我们用 $\mathit{MM}(G)$ 表示图 $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 \notin [l, r]$ 且 $i \notin [L, R]$ 的顶点 $i$，以及所有与这些顶点关联的边。

请计算对所有满足 $1 \le l \le r \le n$ 和 $n+1 \le L \le R \le 2n$ 的整数四元组 $(l, r, L, R)$，$\mathit{MM}(G'(l, r, L, R))$ 的总和。

The first line contains one integer $n$ ($2 \le n \le 1500$) — the number of vertices in each part.

Then $2n$ lines follow, each denoting an edge of the graph. The $i$-th line contains two integers $x_i$ and $y_i$ ($1 \le x_i \le n$; $n + 1 \le y_i \le 2n$) — the endpoints of the $i$-th edge.

There are no multiple edges in the given graph, and each vertex has exactly two incident edges.

第一行包含一个整数 $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$ 条边的两个端点。

给定图中不存在重边，且每个顶点恰好关联两条边。

Print one integer — the sum of $\mathit{MM}(G(l, r, L, R))$ over all tuples of integers $(l, r, L, R)$ having $1 \le l \le r \le n$ and $n+1 \le L \le R \le 2n$.

输出一个整数——对所有满足 $1 \le l \le r \le n$ 和 $n+1 \le L \le R \le 2n$ 的整数四元组 $(l, r, L, R)$，求 $\mathit{MM}(G(l, r, L, R))$ 的总和。