요트 경주

원형 호수에서 매년 요트 경주가 열린다. 호숫가를 따라 반시계 방향으로 1번부터 N번까지 번호가 매겨진 N개의 항구가 있다.

경주 경로는 서로 다른 항구들을 차례로 방문하는 경로이며, 같은 항구를 두 번 방문할 수 없다. 경로에서 연속한 두 항구를 잇는 각 구간을 스테이지라고 하며, 두 항구를 잇는 직선(현)을 따라 항해한다. 따라서 스테이지의 개수는 방문한 항구의 수보다 1 적다.

요트가 임의의 두 항구 사이를 항상 곧장 항해할 수 있는 것은 아니다. 각 항구 A에 대해, A에서 직선으로 곧장 갈 수 있는 항구들의 목록이 주어진다.

모든 스테이지는 직선(현)이므로 두 스테이지가 기하학적으로 서로 교차할 수 있다. 충돌을 피하기 위해, 원칙적으로 모든 스테이지는 서로 교차하지 않아야 한다. (두 스테이지가 한 항구를 공통 끝점으로 공유하기만 하는 경우는 교차로 보지 않는다.)

올해는 새로운 기술 덕분에 교차를 최대 한 번 허용할 수 있는데, 단 그 교차가 맨 첫 번째 스테이지와 얽혀 있을 때에만 가능하다. 구체적으로, 경로가 항구 S에서 출발하고 첫 스테이지가 항구 T로 향한다면, 다른 스테이지 중 최대 하나만 선분 S–T와 교차할 수 있고, 그 밖의 어떤 두 스테이지도 서로 교차해서는 안 된다. 주최 측은 이 '한 번 교차' 허용을 사용할 수도 있고, 아무 교차도 없는 고전적인 방식을 유지할 수도 있다.

요구된 형태의 경로 중에서 스테이지 수가 가장 많은 경로를 구하라.

첫째 줄에 두 정수 N과 k가 주어진다 (1 ≤ N ≤ 500). N은 항구의 수이다. k는 요구되는 형태를 지정한다. k = 0이면 경로는 고전적인 형태(교차가 전혀 없음)여야 하고, k = 1이면 위에서 설명한 대로 첫 스테이지와 얽힌 교차를 최대 한 번 포함할 수 있다.

다음 N개의 줄에는 각 항구에서 직접 갈 수 있는 목적지가 주어진다. i + 1번째 줄에는 항구 i에서 직선으로 갈 수 있는 항구들이 공백으로 구분되어 나열되며, 마지막에 하나의 0으로 끝난다 (목적지가 없을 수도 있다).

두 줄을 출력한다.

첫째 줄에는 요구된 형태의 경로가 가질 수 있는 스테이지의 최대 개수 M을 출력한다.

둘째 줄에는 M개의 스테이지를 달성하는 모든 경로 중에서 출발 항구 번호가 가장 작은 값을 출력한다. 스테이지를 하나도 만들 수 없어 M = 0인 경우에는 1을 출력한다.

예제에 대한 최적 경로 하나를 나타낸 그림이다.