|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||7||2||2||28.571%|
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 the path are called neighbors.
The entrance to the park is near the lawn number one which will be called the entrance lawn. Vasya's parents are very concerned about his safety, so they allow him to play only on the lawn that is a neighbor to the entrance lawn. Entrance lawn is usually overcrowded, so Vasya can't play on it.
Vasya finds it boring to simply walk along the path to the 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 the lawn neighboring to the entrance lawn.
Every day Vasya wants to choose a new walk he hasn't taken before. Help him to determine how many ways are to begin his journey at the entrance lawn, follow exactly three different paths, and find himself on the lawn neighboring to the entrance lawn.
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.
Print the number of walks that Vasya can take.
10 14 1 5 2 5 5 6 2 3 1 3 2 4 4 6 1 6 1 7 7 8 8 1 1 10 9 10 9 8
3 3 1 2 2 3 3 1