Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
System
Time Limit: 2000MSMemory Limit: 30000K
Total Submissions: 312Accepted: 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]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator