2853 「CEOI2012」帆船比赛

译自 CEOI 2012 Day1 T3「Sailing Race」

一年一度的帆船比赛在一个圆形的湖上举行。湖周围有 $N$ 个港口，逆时针方向从 $1$ 到 $N$ 编号。

比赛由几个赛段组成，每个赛段是从一个港口到另一个港口的线段，赛道最多只能到达一个港口一次。组织者想要创建一个包含尽可能多的赛段的赛道。他们必须记住，在一个特定港口的帆船可能只能以直航的方式前往某些特定的港口。幸运的是，对于每个港口 $A$，他们都有从 $A$ 出发的直达目的地的列表，即帆船可以从 $A$ 出发直线到达的其他港口的列表。通常，赛道由不相交的阶段组成，以避免帆船的碰撞。

然而，今年有了一项新技术，如果这条赛道位于第一阶段，那么它可能会允许一条赛道穿过它。所以如果赛道从 $S$ 港开始，赛道上的下一个港口是 $T$，那么最多有一个赛段可以从第一赛段 $S-T$ 中穿过。组织者可能会决定允许这样的十字路口出现，或者选择不交叉的经典设计。

你需要编写一个程序，计算给定类型的赛道，其中包含尽可能多的赛段。

输入的第一行包含两个整数，第一个 $N$ 为港口数量，第二个 $k$ 为所需赛道类型。如果 $k$ 为 $0$，则需要使用经典赛道（无交叉），而如果 $k$ 为 $1$ 则赛道中最多可以包含一个交叉，如上所述。

接下来的 $N$ 行包含从港口出发的直接目的地的列表。第 $(i + 1)$ 行包含港口 $i$ 的列表，有若干个由空格分隔的整数，以 $0$ 结束。

输出的第一行包含一个整数 $M$，这是给定类型的赛道可以包含的最大赛段数。第二行包含一个这样的赛道的起始港的标识符编号。如果有多个解决方案，输出任意一个即可。

• 对于 $40\%$ 的数据，$k = 0$；
• 对于 $50\%$ 的数据，$N \leq 100$；
• 对于 $100\%$ 的数据，$1 \leq N \leq 500$。