ADACHERY - Ada and Cherry

As you might already know, Ada the Ladybug is a farmer. She grows cherry and now she wants to collect them. She is wondering about the number of cherries she will collect. But before you could help here, you shall know some biological facts:

Firstly, almost everyone think that cherry-tree is a tree. But it might not be true - in fact, it is a graph.

Secondly, you have to know, how a cherry looks like. It is not hard to recognize a cherry - it is a node, which is connected to another two nodes, which are NOT connected.

NOTE: Even though the cherry-tree structure might be weird, note that there won't be any multi-branches nor self-branches. Anyway do not assume it is not a cherry-forest.

This is a cherry:

Cherry

This is NOT a cherry:

Not a cherry

 

Input

The first line contains two integers 1 ≤ N, M ≤ 105, the number of nodes of cherry-tree and the number of branches (edges) connecting them.

The next M lines contains two integers 0 ≤ a, b < N, the branch connecting two nodes.

Output

Print a single line - the number of cherries on the cherry-tree.

Example Input

4 2
1 2
3 2

Example Output

1

Example Input 2

5 4
1 2
1 3
1 4
1 0

Example Output 2

6

Example Input 3

6 6
0 1
0 2
2 1
0 3
1 4
5 3

Example Output 3

5

Added by:Morass
Date:2017-07-25
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2020-10-29 12:53:21
I was thinking of some algo and didn't find any clue then i thought it mathematically and got the logic and then just implementation . Classical Problem but great thinking
2019-05-11 12:49:58
@pawanrocks
Here is Input 3

3--5
|
0
/ \
1---2
/
4

As you can see there is only 5 cherries
4, 1, 2
4, 1, 0
5, 3, 0
3, 0, 2
3, 0, 1
Cherry is tree with 3 nodes or triangle without third side.


Last edit: 2019-05-13 14:40:10
2019-05-10 15:09:11
Can somebody please explain how the example output 3 is 5.
2017-11-12 14:07:11
Classic problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.