Walk of Three

Interview

Time limit1sMemory limit512 MB

Summary

Count walks of exactly three edges that start at vertex 1 and end at a neighbor of vertex 1 in a simple undirected graph.

Level: Medium5 of 10
Topics: Graph, Combinatorics, Implementation, Math
Solved: No attempts yet

Problem

The city where Vasya lives has a park with $n$ lawns connected by $m$ paths. One can walk in both directions along each path. The lawns connected by a path are called neighbors.

The entrance to the park is near the lawn number one, which is called the entrance lawn. Vasya's parents are very concerned about his safety, so they allow him to play only on a lawn that is a neighbor to the entrance lawn. The entrance lawn is usually overcrowded, so Vasya cannot play on it.

Vasya finds it boring to simply walk along the path to a neighbor lawn. Instead, he starts at the entrance lawn, and walks along exactly three different paths. After that he plays on the lawn where he ends his walk. Vasya does not break the rules set by the parents, so he always ends his walk on a lawn neighboring the entrance lawn.

Every day Vasya wants to choose a new walk he has not taken before. Help him determine how many ways there are to begin his journey at the entrance lawn, follow exactly three different paths, and find himself on a lawn neighboring the entrance lawn.

Input

The first line of input contains two integers $n$ and $m$ , the number of lawns and the number of paths, respectively ( $1 \leq n \leq 100\,000$ , $1 \leq m \leq 200\,000$ ).

The next $m$ lines contain pairs of lawns connected by paths. Any two lawns are connected by no more than one path. There are no paths connecting a lawn to itself.

Output

Print the number of walks that Vasya can take.

Examples2

Example 1

Input

Expected output

Example 2
Input
```
3 3
1 2
2 3
3 1
```
Expected output
```
0
```