称题目给定的边为特殊边。

称有向边 $(u,v)$ 指向点 $w$，当且仅当 $v$ 在 $u$ 到 $w$ 的路径上。

原问题转化为（转化过程略）：选定一条特殊边为“根边”，对于所有度数 $\ge2$ 的点，指定该点的两条无序的不同的指向外的“关联边”（这两条边分别是新图上，该点所有出边连成的链的起点和终点），使得至少有一条“关联边”指向“根边”上的点（与“根边”重合也可以），的方案数再乘以 $\prod_{i=1}^{n}(deg_{i}-2)!$（链上的其他点的顺序）。

如果只有一条特殊边，那么每个点连出的“关联边”仅有一条有限制，另一条有 $deg_i-1$ 种方案，答案为 $\prod_{i=1}^{n}(deg_{i}-1)!$。

如果有 $k$ 条特殊边，那么会算重，考虑容斥，即考虑一个特殊边集 $S$，求有多少种方案，使得 $S$ 中任意元素均可以成为其“根边”，乘以容斥系数 $(-1)^{\lvert S\rvert}$。

若这 $k$ 条特殊边不在同一条链上，显然无解，不需考虑。

若这 $k$ 条特殊边在同一条链上，则它们对应的系数会被消掉（这是最大疑点，我没有证，只是感性理解），除非 $k=2$ 且这两条边构成的链上没有其他边（可以和其他边有交，只是不能包含）。

此时，把所有特殊边断掉，记录每个点被几条特殊边经过（记为 $ddeg_i$），考虑同一个连通块内的所有从 $x$ 到 $y$ 的链，将这条链上每一个点的 $\frac{1}{deg_i-1}$ 相乘，再乘以 $ddeg_xddeg_y$（$x=y$ 时为 $\binom{ddeg_x}{2}$）为该链的权值，通过树形 DP 求出所有链的权值和 $sum$。

答案为 $(k-sum)\prod_{i=1}^{n}(deg_{i}-2)!$。

过了所有样例，但是题解区没看到类似做法，怀疑正确性。