U138348 间谍网

$Seaway$所效命的$Alpha$国和邪恶的$Euler$国间最终还是爆发了战争。战争爆发前，$Alpha$国就一直对$Euler$国进行间谍渗透。现在战争爆发了，$Euler$国大肆捕捉$Alpha$国的间谍们。为了在保护勇士们的安全的同时继续进行情报收集，$Seaway$被任命为$Alpha$国国家情报局局长，负责重构安插在$Euler$国的间谍网......

众所周知，每个间谍都有自己的上下线。间谍间的上下线关系构成了间谍网。显然，所有间谍都在同一个间谍网内。但是，这个网络非常冗杂。这种冗杂的上下线关系增加了间谍暴露的风险。现在，$Seaway$想知道，最少有多少对上下线关系能够保证间谍网的畅通。并且，在间谍网中，有一类间谍至关重要，他们被称作“末梢间谍”。他们只有一个上线，没有任何下线。$Seaway$非常关心这类间谍的数量。经过分析，$Seaway$认为，在构成整个间谍网的$N$个间谍中，这样的间谍应该有恰好$K$个。现在，你的任务是：在原始间谍网（$N$个间谍，$M$对上下线关系）中删除若干对上下线关系，留下最少的上下线关系保证间谍网畅通，并且满足有$K$个末梢间谍。显然，这个任务有许多种解决方案。如果有一对上下线关系在第一种方案中被删除而在第二种方案中没被删除，那么我们认为这两个方案不同。你只需要给出全部的方案数。

无

无

【**数据范围**】 对于$20\%$的数据，保证$M=N-1$。 对于全部数据，$3\le N\le 10,N-1\le M\le N(N-1)/2,2\le K\le N-1$。