← 返回题目列表

Codeforces · 1651/E

E. 匹配总和

中文机器翻译题面 查看原题

让我们将图形 $$$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]$$$ 以及与这些顶点相关的所有边。

计算所有具有 $$$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))$$$ 之和。

输入

第一行包含一个整数 $$$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$$$。

示例

输入 #1

5
4 6
4 9
2 6
3 9
1 8
5 10
2 7
3 7
1 10
5 8

输出 #1

314