P2144 [FJOI2007] Rotavirus

There are many variants of rotaviruses. Many rotaviruses are generated from a wheel base. An $n$-wheel base consists of $n$ distinct base atoms on a circular ring and one core atom at the center. An edge between $2$ atoms represents the information channel between these $2$ atoms, as shown in Figure 1. The generation rule of an $n$-rotavirus is to delete some edges in the $n$-wheel base so that there is a unique information path between any two atoms. For example, there are $16$ different $3$-rotaviruses, as shown in Figure 2. Given $n\ (n \le 100)$, write a program to compute how many different $n$-rotaviruses there are. 

The first line contains $1$ positive integer $n$.

Output $1$ line, the number of different $n$-rotaviruses.

Translated by ChatGPT 5