The Phantom Troupe wants to sabotage Santa's workshop! To start, they begin by scouting out the area, and discover that it's made up of factories numbered from to with bidirectional conveyer belts between them. Due to the workshop's advanced security technology, the Phantom Troupe can only afford to destroy one conveyer belt. However, this might be enough! If the destroyed bridge disconnects the factories, then Santa's workshop will no longer work. Can you find the number of conveyer belts that the Phantom Troupe can destroy to disconnect the workshop?
Santa's workshop is considered disconnected if there is some pair of factories that cannot reach each other via some path of working conveyer belts
Note: The intended solution for the second subtasks uses topics not yet covered in the lessons this year
Constraints
Subtask 1 [80%]
Subtask 2 [20%]
Input Specification
The first line contains two integers, and .
The next lines each contain two integers, and , indicating a conveyer belt between node and . Each unordered pair is unique.
Output Specification
One integer: the number of conveyer belts that the Phantom Troupe can destroy to disconnect the workshop
Sample Input
6 6
1 2
1 3
2 4
3 5
5 1
4 6
Sample Output
3
Sample Explanation
The graph looks like this:
There are 3 conveyer belts that can be destroyed to disconnect the workshop: 1 2
, 2 4
, and 4 6
.
Comments