시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 128 MB | 2005 | 395 | 203 | 16.175% |
상근이네 반에는 총 K명의 학생이 있다. 그 중 일부는 서로를 엄청나게 싫어한다. 서로 싫어하는 친구는 교실 밖에서 절대 마주치지 않는 경로를 이용해 교실로 이동하려고 한다. 이런 경로를 찾아보자.
입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 찾아야하는 경로의 수 K와 교차로의 수 N이 주어진다. 교차로는 1번부터 N번까지 번호가 매겨져 있다. 다음 N개 줄에는 각 교차로가 어떤 교차로와 연결되어 있는지 주어지며, 교차로 번호가 증가하는 순서로 주어진다. 모든 교차로는 적어도 한 교차로와 연결되어 있다.
입력의 마지막 줄에는 0 0이 주어진다.
1 ≤ K ≤ 100, 2 ≤ N ≤ 5000이며 모든 학생은 1번 교차로에서 시작하고, 교실은 2번 교차로에 있다.
각 테스트 케이스마다 "Case #:" 형식으로 케이스 번호를 출력한다. 그 다음, K개의 겹치지 않는 경로 (1번에서 출발해 2번으로 도착하는 경로)가 존재하면 K개 줄에 각 경로를 출력한다. 없는 경우에는 "Impossible"을 출력한다.
각 테스트 케이스의 정답을 출력한 다음에는 빈 줄을 하나 출력한다.
3 5 3 4 5 3 4 5 1 2 1 2 1 2 4 5 3 4 5 3 4 5 1 2 1 2 1 2 0 0
Case 1: 1 3 2 1 4 2 1 5 2 Case 2: Impossible
University > The MIT Programming Contest > 2008-09 > MIT Programming Contest Individual Round 2008 4번