1651E - Sum of Matchings - CodeForces Solution

import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

n = int(input())
m = 2 * n
G = [[] for _ in range(m + 1)]
for _ in range(m):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
visit = [0] * (m + 1)
inf = pow(10, 9) + 1
ans = 0
for i in range(1, n + 1):
    if visit[i]:
        continue
    u = [i]
    visit[i] = 1
    j = i
    ok = 1
    while ok:
        ok = 0
        for k in G[j]:
            if not visit[k]:
                ok = 1
                visit[k] = 1
                u.append(k)
                break
        j = u[-1]
    l, r = [inf, inf], [-inf, -inf]
    lu = len(u)
    for j in range(lu):
        l[j % 2] = min(l[j % 2], u[j])
        r[j % 2] = max(r[j % 2], u[j])
    c = l[0] * (n - r[0] + 1) * (l[1] - n) * (m - r[1] + 1)
    ans += c * lu // 2
    for j in range(lu):
        l, r = [inf, inf], [-inf, -inf]
        for k in range(j, j + 2):
            l[k % 2] = min(l[k % 2], u[k % lu])
            r[k % 2] = max(r[k % 2], u[k % lu])
        x = u[(j - 1) % lu]
        for k in range(j + 2, j + lu):
            y = u[k % lu]
            ok = 1
            for v in range(2):
                if l[v] < x < r[v] or l[v] < y < r[v]:
                    ok = 0
                    break
            if ok:
                l1, r1 = [1, l[0]], [r[0], n]
                l2, r2 = [n + 1, l[1]], [r[1], m]
                c = ((k - j) % lu) // 2
                for l0, r0 in [l1, l2]:
                    if l0 <= x <= r0:
                        l0 = max(l0, x + 1)
                    if l0 <= y <= r0:
                        l0 = max(l0, y + 1)
                    c *= r0 - l0 + 1
                for l0, r0 in [r1, r2]:
                    if l0 <= x <= r0:
                        r0 = min(r0, x - 1)
                    if l0 <= y <= r0:
                        r0 = min(r0, y - 1)
                    c *= r0 - l0 + 1
                ans += c
            l[k % 2] = min(l[k % 2], u[k % lu])
            r[k % 2] = max(r[k % 2], u[k % lu])
print(ans)