题目描述

一个 $n$ 个点构成的竞赛图中最多能有多少条哈密顿路径？

$n$ 最多能做到多大？

样例输入

 4

样例输出

 5

样例解释

 边的朝向分别为
 1->2
 2->3
 3->4
 4->1
 1->3
 2->4
 时

 哈密顿路径分别为
 1->2->3->4
 2->3->4->1
 3->4->1->2
 4->1->2->3
 2->4->1->3

 共5条

 P.S.经过爆搜发现n=1~9时答案分别为1,1,3,5,15,45,189,661,3357