#P2859. [Ceoi2012]Sailing Race

    ID: 1971 传统题 1000ms 256MiB 尝试: 5 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-环形区间 DP消除被支配候选暴力枚举鸣谢Oimaster

[Ceoi2012]Sailing Race

题目描述

在一个圆环上,有 nn 个地点,这些地点按照逆时针顺序用正整数 11 到 nn 编号。

有些地点间存在直线道路可以到达,但道路并不是双向的,也就是说如果存在 aa 到 bb 的道路,不一定同时存在 bb 到 aa 的道路。

现在你要从某个地点开始,沿着道路走,每个地点最多被经过一次,并且你走过的道路对应的线段只能在公共端点处相交。

但是有时候允许一些特例,具体说就是你走过的某条道路可以和最初走的道路相交最多一次。

你的任务是求出最多能走过的道路数,并给出一个可行的起点。

输入格式

第一行两个非负整数 n,kn,k。如果 k=0k=0 表示不允许特例,k=1k=1 表示允许特例。

下面 nn 行,依次描述每个地点可以到达的地点编号。每行以 00 结束。

输出格式

第一行一个非负整数 tt,表示最多可以走的道路数。

第二行一个正整数 ss,表示一个可行的起点编号。

如果存在多个起点满足要求,输出其中任何一个都可以。

7 1
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0
5
2

数据规模与约定

对于 100%100\%​ 的数据,1≤n≤5001\leq n\leq 500。