让我们将图形 $$$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