CodeLand

0

0 votes
Problem

CodeLand is a big country. It consists of N cities and M two sided roads. Despite being big, the cities of CodeLand are well connected with each other, i.e there is always a way to reach from any given city to any other city. Now, the government of CodeLand has decided to partition the country into states to easily handle the administration of the country. They follow a simple strategy to form states out of CodeLand. A state is a maximal group of cities such that for every city in a state, if it is removed, there is still path from every city remaining in the state to every other city in the state. The states may or may not have overlapping cities.

The government is not concerned about the non-disjoint nature of the states. Instead, they are planning to establish bi-directional air way between states which do not have any overlapping cities. This means that the states which do not have any overlapping cities will have exactly one air way between them. The probable chief architect for this probable project is asked to find the feasibility of this project. To calculate the feasibility of the project, the architect decides to find the total number of air ways that would have to be established. Please help the architect in finding that number.

Input :
First line contains number of cities N and number of road networks M.
The next M lines contains two cities A and B (integers) representing the ends of the road. The cities are numbered from 1 to N. There will be no multiple edges or self-loops

Output :
Number of air networks that needs to be established

Constraints :
1 <= N <= 10^5
0 <= M <= 10^5
1 <= A,B <= N

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The states formed are {1,2}, {2,3}, {3,4}. Here only {1,2} and {3,4} do not have any overlapping city, Hence 1 air network is needed.

Editor Image

?