- Practice
- Mathematics
- Probability
- Connect the country

# Connect the country

# Connect the country

We have a country containing _N _cities. Each day we choose 2 cities such that there is no road between them and build a road between them. We choose each pair of nonadjacent cities with equal probability. Let X be the number of days before we obtain a connected country. What is the expected value of X? Output the integer part of answer.

**Input Format**

First line of input as an integer N.

**Constraints**

**Output Format**

Print an integer being the result of the test.

**Sample Input 0**

```
3
```

**Sample Output 0**

```
2
```

**Explanation 0**

In the first example, first two roads are sufficient for connecting the cities so the answer would be 2.

**Sample Input 1**

```
4
```

**Sample Output 1**

```
3
```

**Explanation 1**

In the second example if the first three roads of the country are edges of a triangle, then we need a fourth road to make the country connected, otherwise the country would be connected with first three roads. The probability of the former situation is 4/20 (number of triple of roads that make a triangle divided by number of ways we can choose 3 different roads), and the probability of later situation is 16/20. So the result would be 4/20*4 + 16/20*3 = 3.2 and since you have to print only the integer part as output, print 3