#P18501. Football in Osijek
Football in Osijek
Football in Osijek
著名的 Osijek 竞赛训练营越来越受欢迎,还开设了其它训练营,其中包括 Osijek 足球训练营。Osijek 足球杯即将举行,训练营希望组建一支队伍,但规则严格要求队伍恰好包含 名球员。
训练营有 名球员,编号为 。球员 的偏好是:
如果我加入队伍,球员 也必须加入。
允许 ,这表示该球员只关心自己。
此外,每名球员还有一个要求:
我不想与和我之间没有偏好链联系的人在同一支队伍。
偏好链是一个球员序列 ,其中每一步的下一个球员都是当前球员偏好指向的球员,即从当前球员 走向 。两名球员 有联系,当且仅当存在一条从 到 的偏好链,或者存在一条从 到 的偏好链。
换言之,合法队伍既要满足所有入队球员的偏好闭包,又要满足队伍中任意两名球员至少在上述一个方向上可达;这里只看无向连通不足以满足要求。
遗憾的是,规则中的 尚未确定。你需要分别考虑 的所有情况:如果原来无法组建这样的队伍,可以与球员会面,劝说其修改偏好。
一次会面可以任选 ,将 改为 。修改后仍允许 。
对于每个 ,求为了能够组建一支恰有 人的合法队伍,最少需要多少次会面。各个 的场景相互独立,都从输入给出的原偏好开始考虑。
输入格式
第一行一个整数 (),表示球员人数。
第二行包含 个整数 (),表示原来的偏好。
输出格式
输出一行 个整数,第 个整数表示组建恰好 人的合法队伍所需的最少会面次数。
完整原样例
5
2 3 1 3 5
0 1 0 0 1