Problem Description

The road network of Bit Town consists of $n$ intersections connected by $m$ bidirectional roads.

Recently, Bit Town has been awarded the hosting rights for a duathlon championship. The race consists of two segments: a running segment followed by a cycling segment.

The race route is to be planned as follows:

1. Select three distinct intersections $s$, $c$, and $f$, which will serve as the starting point, the transition point (where athletes switch from running to cycling), and the finishing point, respectively.
2. Choose a path that starts at $s$, passes through $c$, and ends at $f$. For safety reasons, the chosen path must visit each intersection at most once.

Before finalizing the route, the mayor would like you to calculate the total number of different ways to select $s$, $c$, and $f$ such that there is at least one feasible path meeting the requirements in step 2.

Input Format

The first line contains two integers $n$ and $m$, representing the number of intersections and the number of bidirectional roads, respectively.

The following $m$ lines each contain two integers $v_i$ and $u_i$, indicating that there is a bidirectional road 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 Format

Output a single line containing an integer, which is the number of different ways to select $s$, $c$, and $f$ that meet the requirements.

Sample Input and Output

Sample Input #1

4 3
1 2
2 3
3 4

Sample Output #1

8

Sample Input #2

4 4
1 2
2 3
3 4
4 2

Sample Output #2

14

Notes/Hints

Hints

In the first example, there are 8 different ways to choose $(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 example, there are 14 different ways to choose $(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 (Note: These subtasks are provided for reference and are not related to the final evaluation of this problem)

• 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 at most the endpoint of two bidirectional roads.
• Subtask 4 (points: $10$): $n \leq 1000$, the road network does not contain any cycles.
• Subtask 5 (points: $13$): $n \leq 100000$, the road network does not contain any cycles.
• Subtask 6 (points: $15$): $n \leq 1000$, each intersection is contained in at most one cycle.
• Subtask 7 (points: $20$): $n \leq 100000$, each intersection is contained in at most one cycle.
• Subtask 8 (points: $8$): $n \leq 1000$, $m \leq 2000$.
• Subtask 9 (points: $10$): $n \leq 100000$, $m \leq 200000$.

见题面 Input 部分

见题面 Output 部分