Problem I
Pong Tournament
The Swedes wanted to arrange a ping pong tournament among the $n$ high school students in the nation. Since Sweden is the fairest country on earth, they wanted to ensure that the ranking of all the players is perfectly fair. Therfore, they decided that every high school student in the nation should play against every other high school student. Sadly, when all the matches were done, it turned out that ranking the players in a fair manner was hard, or even impossible; sometimes it was the case that a player $a$ had beat some other player $b$, player $b$ had beat some player $c$ and player $c$ had beat player $a$. Regardless of which ranking the Swedish experts suggested, someone was treated unfairly in the sense that they were ranked below someone they had beaten. The Swedish king thus decided to disqualify some players, so that there would be no ambiguity in the ranking among the remaining players. His experts then came up with a set $S$ of $k$ players to disqualify. Unfortunately, you are one of these disqualified players.
Together with the other disqualified players, you plead with the king to make him undo his decision. While he remains firm in the belief that his approach will yield a fair ranking, he has offered your group a deal: If you can find a set $S’$ containing strictly less than $k$ players to disqualify instead of your own group, then the king will disqualify this group instead. The group $S$ of disqualified players has now bestowed upon you the responsibility of finding that different group $S’$. They require that none of the originally disqualified players are in $S’$, and that the group you suggest is as small as possible.
Input
The first line contains two positive integers, $n$ the number of high school students, and $k$ the number of disqualified players. Then follows $n$ lines, each containing $n$ integers. The $j$-th integer on the $i$-th line is $1$ if player $i$ beat player $j$, and $0$ otherwise (i.e. there is also a $0$ at the $i$-th entry of the $i$-th line, even though player $i$ didn’t lose to himself). Finally, there is a line with $k$ integers indicating the set $S$, the players who were disqualified. Each player is identified by a number between $0$ and $n-1$. You may assume that, when the disqualified players $S$ are removed, there exists a fair ranking of the remaining players. A fair ranking is one such that nobody is ranked below someone they beat. We remark that even though the Swedish experts couldn’t find a fair ordering of all the players, there might still be one. Note: The input may be quite large.
We always have $2 \leq k \leq n \leq 2\, 000$.
Output
Output a single integer, the size $k’$ of the smallest set $S’$ of players needed to be disqualified to make a fair ranking. Recall that none of the originally disqualified players of $S$ can be in $S’$, and $k’$ must be strictly less than $k$. If no such solution exists, print “impossible”.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 0 0 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 2 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 2 0 0 1 1 1 0 0 1 0 1 0 0 0 0 1 0 1 2 |
impossible |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 3 0 1 1 0 1 0 0 1 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0 1 2 |
2 |
