正经的写一篇题解吧。这个题目求的是有标号的n个点n条边的联通图的数量。n <=5000
往往题目异常简洁的题目会比较难>_<。。。
分析1：
这个图必然是一个环加上一个外向树的形式。
思路1 or 2：
那么接下来就有两个思路了，要么固定环，想办法算出答案，要么选一个点为根，在这个有根树中考虑这个环。
思路1：
尝试固定环，设环大小为k，那么在这个图中去掉这些环上的边，得出的就是n个点，k棵树的森林。
令F(n,k)表示n个点，k棵树的森林的个数，那么环大小为k的情况答案是：
F(n,k)*k!/2。。这不难理解。。因为森林出来之后森林的那些根的园排列有k!/2种。
考虑如何求F(n,k)。
思路 1.1 or 1.2：
要么将F(n,k)看成一个二维递推式，推导出结果。 要么尝试使用组合数学的方法直接计算出F(n,k)。
思路 1.1：
考虑一棵树，为了在递推中不影响树的大致的整体结构（最大相似性决定递推的成功>_<）。我们可以
尝试取走一个叶子来将树的大小-1
那么令G(n,t)表示n个节点，t个叶子的树的个数。
考虑两种规划的方式，正向和逆向，逆向规划（即在算G(n,t)时用以前的结果）的关键在于取走一个叶子之后，不能知道叶子的父亲是否
会变成叶子，而叶子数是很重要的，所以不可行。正向规划相反则是可行的（即用G(n,t)更新G(n+1,..)的）结果。
考虑当前是G(n,t)，如果加入一个叶子，那么可以连到叶子节点上，也可以连到非叶子节点上。
前者叶子数不变，后者叶子数+1。就可以较方便的计算了。
但是每个G(n,t)在计算的时候，它的每个叶子都会把它的结果计算一遍，所以最后要除以t。
但是这是n^2的，而且还涉及高精度的问题。所以不是一个好算法。
思路 1.2：
在推导标号树个数的时候有一种方法叫双重计数，同样可以解决计算F(n,k)的问题。
并能给出一个直接的公式
没时间就不展开了。。。可以自己去看wiki
复杂度是O（N）。
http://en.wikipedia.org/wiki/Double_counting
思路2：
令1为根，那么我们可以找到环中最接近1的点（注意，满足唯一性！计数问题必不可少的）
令其为x，考虑x在环上的两个相邻点l和r。
令l<r。。去掉边x->r。就变成了一棵树，还是以1为根可以发现l是r的祖先。
可以发现在“1为根，x在环上的相邻点是l和r且l<r的结果” = “1为根，l<r且l是r的祖先的树的个数”
那么后者的结果乘以每句l和r造成的C(n-1,2)就是答案。
如何求后者呢？
有一种prufer Code的推广形式能轻易的给出答案。。由于非常繁琐就不说了。。
http://www.cs.elte.hu/egres/tr/egres-05-16.pdf
。。。我发现写这么多还不如直接贴5、6个网址让大家自己去看。。。。
我2。。。。
。。