Roads in the Kingdom#190
In a kingdom, there are cities. To allow all residents to travel freely, the cities must be connected by roads in such a way that it is possible to travel from any city to any other city.
However, according to the kingdom's main law, every year all roads are destroyed and rebuilt in a new way. Each year's road configuration must be unique and must not repeat any configuration used before.
Legend has it that if, in any year, it becomes impossible to create a new configuration, the kingdom will be conquered. Your task is to determine how many years the kingdom can avoid being conquered.
A single integer — the number of cities (1 \leq N \leq 75).
Output the number of years the kingdom will last.
Example 1