P4630 [APIO2018] Triathlon

Bit Town’s road network consists of $n$ intersections connected by $m$ bidirectional roads. Recently, Bit Town obtained the right to host a triathlon championship. The race has two stages: contestants first complete a long-distance running stage, and then ride a bicycle to complete the second stage. The race route must be planned as follows: 1. First, choose three pairwise distinct intersections $s$, $c$, and $f$, as the start point, the transition point (after reaching this point during the running stage, athletes ride a bicycle to the finish), and the finish point. 2. Choose a path that starts from $s$, passes through $c$, and finally reaches $f$. For safety reasons, the chosen path visits each intersection at most once. Before planning the route, the mayor wants you to help compute how many different ways there are to choose $s$, $c$, and $f$, such that in step 2 there is at least one path that satisfies the requirement.

The first line contains two integers $n$ and $m$, representing the number of intersections and the number of bidirectional roads. The next $m$ lines each contain two integers $v_i, u_i$, indicating that there is a bidirectional road directly connecting intersections $v_i$ and $u_i$ ($1 \le v_i, u_i \le n$, $v_i \neq u_i$). It is guaranteed that any two intersections are directly connected by at most one bidirectional road.

Output one line containing one integer, the number of different ways to choose $s$, $c$, and $f$ that satisfy the requirement.

**Hint** In the first sample, there are the following $8$ different choices of $(s, c, f)$: - $(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (3, 2, 1)$; - $(4, 2, 1), (4, 3, 1), (4, 3, 2)$. In the second sample, there are the following $14$ different choices of $(s, c, f)$: - $(1, 2, 3), (1, 2, 4), (1, 3, 4), (1, 4, 3), (2, 3, 4)$; - $(2, 4, 3), (3, 2, 1), (3, 2, 4), (3, 4, 1), (3, 4, 2)$; - $(4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2)$. **Subtasks** - Subtask 1 (points: $5$): $n \leq 10$, $m \leq 100$. - Subtask 2 (points: $11$): $n \leq 50$, $m \leq 100$. - Subtask 3 (points: $8$): $n \leq 100000$, each intersection is an endpoint of at most two bidirectional roads. - Subtask 4 (points: $10$): $n \leq 1000$, there are no cycles in the road network (a cycle means that there exists a sequence of intersections of length $k$ ($k \ge 3$), $v_1, v_2, \ldots, v_k$, where all intersection labels in the sequence are pairwise distinct, and for $i$ from $1$ to $k - 1$ there is a bidirectional road directly connecting $v_i$ and $v_{i+1}$, and there is also a bidirectional road directly connecting $v_k$ and $v_1$). - Subtask 5 (points: $13$): $n \leq 100000$, there are no cycles in the road network. - Subtask 6 (points: $15$): $n \leq 1000$, each intersection belongs to at most one cycle. - Subtask 7 (points: $20$): $n \leq 100000$, each intersection belongs to at most one cycle. - Subtask 8 (points: $8$): $n \leq 1000$, $m \leq 2000$. - Subtask 9 (points: $10$): $n \leq 100000$, $m \leq 200000$. Translated by ChatGPT 5