题解 | Friend

from math import gcd
from sys import stdin
from bisect import bisect_left
from typing import Tuple, List, Set, Dict


def solve_a(l: List[int]):
    l[0] -= l[4]
    l[1] -= l[5]
    l[2] -= l[6]
    l[3] -= l[7]
    l[0] -= l[2]
    l[1] -= l[3]
    l[4] -= l[6]
    l[5] -= l[7]
    l[0] -= l[1]
    l[2] -= l[3]
    l[4] -= l[5]
    l[6] -= l[7]


def fmt_div(a: int, b: int):
    c = gcd(a, b)
    return f"{a//c}/{b//c}"


def main():
    # Input
    n, m, *rest = map(int, stdin.read().split())
    edges: Set[Tuple[int, int]] = set()
    for _ in range(m):
        u = rest.pop() - 1
        v = rest.pop() - 1
        edges.add((u, v) if u < v else (v, u))
    # Preprocess
    edges_o: List[List[int]] = [[] for _ in range(n)]
    edges_i: List[List[int]] = [[] for _ in range(n)]
    for u, v in sorted(edges):
        edges_o[u].append(v)
        edges_i[v].append(u)
    # Calculate
    KL = [[0, 0, 0, 0, 0, 0, 0, 0] for _ in range(n)]  # 0, 1, 2, 3, 4, 5, 6, 7
    KM = [[0, 0, 0, 0, 0, 0, 0, 0] for _ in range(n)]  # 0, 1, 2, 3, 4, 5, 6, 7
    KR = [[0, 0, 0, 0, 0, 0, 0, 0] for _ in range(n)]  # 0, 1, 2, 3, 4, 5, 6, 7
    for nl, (a, km, kr) in enumerate(zip(KL, KM, KR)):
        nr = n - nl - 1
        a[0b000] = nr * (nr - 1) // 2
        km[0b000] = nl * nr
        kr[0b000] = nl * (nl - 1) // 2
    ll, lx = 0, 0
    for kr, nei, a, neo, km in zip(KR, map(len, edges_i), KL, map(len, edges_o), KM):
        a[0b101] = neo * (neo - 1) // 2
        km[0b001] = lx - ll - nei
        kr[0b011] = nei * (nei - 1) // 2
        kr[0b100] = ll
        ll += nei
        lx += neo
    rr = 0
    for a, neo in zip(reversed(KL), map(len, reversed(edges_o))):
        a[0b010] = rr
        rr += neo
    for u, v in edges:
        blivu = bisect_left(edges_i[v], u)
        blouv = bisect_left(edges_o[u], v)
        KL[u][0b001] += v - u - 1
        KL[u][0b011] += len(edges_i[v]) - blivu - 1
        KL[u][0b100] += n - v - 1
        KL[u][0b110] += len(edges_o[v])
        KM[u][0b010] += u
        KM[u][0b011] += blivu
        KM[v][0b100] += n - v - 1
        KM[v][0b101] += len(edges_o[u]) - blouv - 1
        KM[v][0b110] += len(edges_o[v])
        KR[v][0b001] += v - u - 1
        KR[v][0b010] += u
        KR[v][0b101] += blouv
        for w in edges_o[v]:
            KR[w][0b110] += 1
            if (u, w) in edges:
                KL[u][0b111] += 1
                KM[v][0b111] += 1
                KR[w][0b111] += 1
    for a in KL:
        solve_a(a)
    for a in KM:
        solve_a(a)
    for a in KR:
        solve_a(a)
    for kl, km, kr in zip(KL, KM, KR):
        a1 = kl[0b000] + km[0b000] + kr[0b000]
        a2 = kl[0b010] + km[0b001] + kr[0b100]
        a3 = kl[0b100] + kl[0b001] + km[0b100] + km[0b010] + kr[0b010] + kr[0b001]
        a4 = kl[0b101] + km[0b110] + kr[0b011]
        a5 = kl[0b110] + kl[0b011] + km[0b101] + km[0b011] + kr[0b110] + kr[0b101]
        a6 = kl[0b111] + km[0b111] + kr[0b111]
        aa = a1 + a2 + a3 + a4 + a5 + a6
        print(
            fmt_div(a1, aa),
            fmt_div(a2, aa),
            fmt_div(a3, aa),
            fmt_div(a4, aa),
            fmt_div(a5, aa),
            fmt_div(a6, aa),
        )


main()

令三元组的三个元素从小到大，对于每个顶点，考虑它作为最小/中间/最大，有0-3条边的8种情况。

统计三元环数量的时间复杂度，根据OIWiki，为O(m^1.5)；bisect总共最多为O(mlogn)；总共为O(m^1.5)