\(N\) 頂点を用意し，\(y_i \to x_i\) へと辺を張ったグラフを考えます． このグラフにおいて，各頂点の出次数と入次数は等しいです． また，各頂点について，そこから出る辺には順番が定まっています．

頂点 \(1\) から出発し，辺をたどる操作を考えます．頂点に到達するごとに，次にたどる辺を選択する必要がありますが，これは頂点ごとに定まっている順番をそのまま使うことにします．

この操作はいずれ頂点 \(1\) で終了します． この時頂点 \(1\) に触る辺はすべて使い終わっています． 同じ操作を頂点 \(2,3,\cdots,N\) と繰り返していくと，すべての辺を使い終わります．

この移動の様子を数えることで，元の問題を解くことができます． 出発する頂点を \(1,2,\cdots,N\) と試し，それぞれについて \(dp[i][j]=\) 今頂点 \(i\) にいて \(j\) 回辺をたどった場合の数え上げ　というDPを解けばよいです．

\(x_1\) は，最初にたどる辺の行き先です． これを \(N\) 通りすべて試すと，同じ問題を \(N\) 回解く必要があります． 移動の様子を逆順に見ることで，計算を \(1\) 回にまとめられます．（が，この高速化を行わなくても間に合います．）

計算量は \(O(N^3M)\) です．

解答例(C++)