- 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 *K ^{2}* 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 2^{2} = 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 1^{2} = 1).