- Prepare
- Functional Programming
- Functional Structures
- Prison Transport
Prison Transport
Prison Transport
There are N inmates numbered between [1, N] in a prison. These inmates have superhuman strength because they have drunk a special concoction made by Dr. Evil. They have to be transported by some buses to a new facility. But they are bound by special chains which are made from strong carbon fibres. Each inmate is either chained alone or is chained in a group along with one or more inmates. A group of inmates are those who are directly or indirectly connected to each other. Only one group can be transported per bus.
There are buses which will charge fixed amount bucks for transferring inmates. Charges are directly proportional to the capacity of bus. If a bus charge K bucks then it can carry upto K2 inmates at one time. Buses are available for all positive integral cost ranging from [1, 2, 3, ...]. A bus can be used multiple times, and each time it will charge. Note that a bus can also transfer less number of inmates than it's capacity.
Find the minimal cost to transport all the inmates.
Input
The first line contains N representing the number of inmates. Second line contains another integer, M, number of pairs of inmates who are handcuffed together. Then follows M lines. Each of these lines contains two integers, P Q, which means inmate numbered P is handcuffed to inmate numbered Q.
Output
For the given arrangement, print the minimal cost which can be incurred while transferring inmates.
Constraints
2 ≤ N ≤ 100000
1 ≤ M ≤ min(N*(N-1)/2, 100000)
1 ≤ P, Q ≤ N
P ≠Q
Sample Input
4
2
1 2
1 4
Sample Output
3
Explanation
Inmates #1, #2, #4 are connected to each other (1--2--4
) so they lies in a single group. So a bus of cost 2 (with capacity 22 = 4) is required to carry them. Inmate #3 is not handcuffed with anyother. So he can be transported in a bus of cost 1 (with capacity 12 = 1).