一年一度的帆船比赛在一个圆形湖泊上举行。湖畔有 $N$ 个港口，按逆时针方向从 $1$ 到 $N$ 编号。比赛由多个阶段组成，每个阶段是连接两个港口的一条线段，且比赛航线中每个港口最多只能被访问一次。组织者希望设计一条包含尽可能多阶段的比赛航线。他们需要注意，从某个给定的港口出发，帆船只能通过直航路线前往特定的港口。幸运的是，对于每个港口 $A$，他们都有从 $A$ 出发可以直接到达的目的地列表，即帆船可以从 $A$ 沿直线直接到达的其他港口列表。

通常情况下，为了避免帆船相撞，比赛航线由互不相交的阶段组成。然而，今年引入了一项新技术，允许最多发生一次交叉，且该交叉必须落在第一阶段上。也就是说，如果比赛航线起点为港口 $S$，航线的下一个港口为 $T$，那么整条航线中最多只能有另外一个阶段与第一阶段 $S-T$ 相交。组织者可以决定是否允许这种交叉（$k=1$），或者选择不含任何交叉的经典设计（$k=0$）。

任务

编写一个程序，计算在给定类型下包含最多阶段数的比赛航线。

输入格式

输入的第一行包含两个整数，第一个数 $N$ ($1 \le N \le 500$) 表示港口数量，第二个数 $k$ 表示所需比赛航线的类型。如果 $k = 0$，则需要一条经典航线（无交叉）；如果 $k = 1$，则航线中最多可以包含一次交叉，且该交叉必须如上所述发生在第一阶段上。

接下来的 $N$ 行包含每个港口可以直接到达的目的地列表。第 $i+1$ 行包含港口 $i$ 的列表，是由空格分隔的整数序列，以 $0$ 结尾。

输出格式

输出的第一行包含一个整数 $M$，表示该类型的比赛航线最多可以包含的阶段数。

第二行包含满足该最大阶段数的一条航线的起点港口编号。如果存在多个解，你的程序只需输出其中任意一个。

样例

输入样例 1

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

输出样例 1

5
2

子任务

• 在 $40\%$ 的测试用例中，$k = 0$。
• 在 $50\%$ 的测试用例中，$N \le 100$。
• 仅第一行输出正确不会获得部分分。