Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Language:
System
 Time Limit: 2000MS Memory Limit: 30000K Total Submissions: 314 Accepted: 107

Description

The county where the National Olympiad in Informatics is held this year it is a little bit strange. In the county there are N cities, numbered from 1 to N. Each of the N cities of the county is connected to exactly two other cities, through bidirectional roads. Even stranger is the fact that, inside this roads system it is not always possible to get from every town to any other town walking these roads. Anyway, the inhabitants of the county are very proud of their system and they think there is not another like this. You want to prove them the opposite and for this you want to calculate how many different road systems, with the upper feature, exist. Two systems are considered different if there is at least one road between a pair of cities i and j inside the first system, which does not exist inside the second one.

Write a program that calculates how many different road systems exist.

Input

From the input, you will read the integer value n(3 <= n <= 100), representing the number of cities of the county.

Output

In the output, you will write an integer value, representing the number of different street systems, with the feature that every city is connected through direct streets to exactly two other cities.

Sample Input

`4`

Sample Output

`3`

Source

[Submit]   [Go Back]   [Status]   [Discuss]