题目大意

给出一个n个点的竞赛图，现从中钦定 $k$ 个点，保证将这 $k$ 个点移除后，剩余的图将不存在环。

求出在不移除任何一个钦定的点的情况下，移除一些点使图中没有环的最小所需移除的点数。

如果这个数目大于等于 $k$ 或不存在，输出 impossible。

$2 \leq k,n \leq 1000$

题解

首先钦定的不能删的$k$个点如果成环了显然就没救了。

也就是说，题目保证了钦定的点和没钦定的点构成的生成子图都是DAG。

为了方便描述，接下来把钦定的点称为白点，没钦定的点称为黑点。

首先给出一个关于竞赛图的引理:

对于一个点数为 $n$ 的强联通竞赛图，一定存在大小为$i$的环，其中$3 \leq i \leq n$。

一发简单证明：

$n=3$显然成立，假设$n>3$，随意删除图上的一个点$x$，设剩下的强联通分量分别为$A_1,A_2 ,\cdots, A_n$。

由于原图强联通，那么这些强连通分量显然不会因为删了一个点就不相连，于是这些强联通分量显然是联通的。于是令这些强连通分量的顺序满足若$i<j$，存在$A_i->A_j$的边。

同时由于此图强联通，那么显然存在$x->A_1$以及$A_n->x$。

于是就有了环:$x->A_1->A_2-> \cdots -> A_n -> x$，长度为$n$。

由于删点后剩下的这些强连通分量同样可以这么构造，那么得证、

有了这个引理，目标就变成了删除所有的三元环，因为任意长度大于$3$的环，由于是强连通分量，始终包含三元环。

可以发现，本质不同的三元环只有两种:两黑一白，两白一黑。

两白一黑的话，把唯一的黑的删掉即可。但两黑一白就需要选择删哪个黑划算。

于是考虑搞出黑点和白点的拓扑序，黑点设为$X$，白点设为$Y$。

可以发现，拓扑序中对于任意$i<j$，存在边$i->j$。

不难发现，将$X$扫一遍，对于每个黑点$x$，若存在$i<j,x->i,j->x$，那么找到了一个两白一黑环，删去这样的黑点。

于是现在对于每个剩下来的黑点，满足在$Y$的拓扑序上，所有$x->y$边出现在$y->x$边之后。

那么出现一个两黑一白的条件是，对于$X$中的点，满足$i<j$时，存在节点$y \in Y$，满足 $ y -> x_i , x_j -> y $。

于是记录一下对于每个黑点$x_i$的$x_i->y$边最早出现的位置$f_i$，那么两个黑点不相交的条件为$i < j , f_i \leq f_j$

做个最长不上升子序列，剩下来的就是最多能保留的点。

于是做完了~

代码:

#include
    
     #include
     
      using namespace std;inline int read(){    int x=0;char ch=getchar();    while(ch<'0' || '9'