시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
3.0 초 32 MB 2 0 (0%) 0
문제
Drawing
원모양으로 생긴 호수에서 범선 경주대회가 열린다. 호숫가에는 N개의 항구들이 반시계 방향으로 돌아가며 1부터 N까지의 번호가 붙어있다. 경주는 몇 개의 스테이지로 되어있는데, 각 스테이지는 어떤 항구 다른 항구를 잇는 직선 경로에 해당한다. 전체 경주 경로는 재방문하는 항구 없이 어떤 항구에서 다른 항구로 몇 개의 스테이지를 따라 이동하는 경로라고 할 수 있다. 대회 개최측은 최대한 많은 스테이지를 가지는 경주 경로를 짜고 싶어 한다. 그 경주 경로에 포함될 수 있는 스테이지들의 후보, 즉 각 항구에서 움직일 수 있는 다른 항구들의 목록이 주어지고 대회측은 그 중 몇 개를 이어 붙여 경주 경로를 짠다. 주의할 점은 경기 중 사고를 막기 위해 경주 경로에 포함된 스테이지들은 서로 교차되지 않아야 한다는 것이다. 그런데 며칠 전, 첫 번째 스테이지에는 교차점이 하나 있어도 사고가 나지 않도록 하는 신기술이 개발되었다. 따라서 전체 경주 경로가 S에서 시작하고 바로 다음에 항구 T로 간다면, 첫 번째 스테이지인 S-T와 겹치는 다른 스테이지가 그 경주 경로에 최대 1개까지 있을 수 있다. (물론 그 신기술을 사용하지 않아도 상관 없다.) 위의 조건을 만족하는 경주 경로들 중에 가장 많은 수의 스테이지를 포함하는 경주 경로를 출력하는 프로그램을 작성하라.
입력
표준 입력에서 다음의 입력을 읽는다. 첫 번째 줄에 항구의 수를 나타내는 정수 N(1 $\leq$ N $\leq$ 500)과, k(k=0 혹은 1)이 주어진다. k=0은 신기술을 사용할 수 없는 경우에 대한 답을 출력하라는 뜻이고, k=1은 신기술을 사용할 수 있는 경우(그렇지만 쓰지 않아도 된다)에 대한 답을 출력하라는 뜻이다. 다음 N개의 줄에는 각 항구에서 움직일 수 있는 다른 항구들의 목록이 주어진다. 입력의 (i+1)번째 줄에는 항구 i에서 움직일 수 있는 다른 항구들의 번호가 빈 칸을 사이에 두고 주어지고 마지막으로 0이 주어진다.
출력
표준 출력으로 다음을 출력한다. 첫 번째 줄에 주어진 입력에서 문제 조건을 만족하는 경주 경로들이 포함할 수 있는 최대 스테이지 개수를 출력한다. 두 번째 줄에는 그런 경주 경로의 시작 항구 번호를 출력한다. 만약 그런 시작 항구가 여러 가지라면 아무 답이나 출력해도 상관 없다.
힌트
다음 항목들에 대하여 부분점수를 받을 수 있다. - 테스트 케이스의 30%에 대해 k=0이면서 N$\leq$100이다. - 테스트 케이스의 10%에 대해 k=0이면서 N$\nleq$100이다. - 테스트 케이스의 20%에 대해 k$\neq$0이면서 N$\leq$100이다. - 첫 번째 줄만 맞은 경우에 대한 부분점수는 없다. #### 입력 예시 ``` 7 1 5 0 5 0 7 0 3 0 4 0 4 3 0 2 1 0 ``` #### 출력 예시 ``` 5 2 ```