시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 113 | 37 | 24 | 34.286% |
N마리의 요정들이 일렬로 서서 마법을 쓰고 있다. 어린 마법사 민형이는 텔레포트 마법을 배우기 위하여 요정들의 마법을 일일이 기록하여 연구하고 있다. 민형이는 요정들을 가장 왼쪽에 있는 요정부터 순서대로 1~N의 번호를 매겼다.
요정들은 마법을 이용하여 위치를 바꿀 수 있다. 요정들은 두 가지 마법 중 하나를 사용한다.
예를 들어, 6마리의 요정이 처음에 아래와 같이 있었다고 하자.
[1, 2, 3, 4, 5, 6]
이 상태에서 4번 요정이 마법을 사용하면 다음과 같은 상태로 변한다.
[5, 6, 4, 1, 2, 3]
여기서, 2번 요정과 5번 요정이 동시에 마법을 사용하면 다음과 같은 상태로 변한다.
[2, 6, 4, 1, 5, 3]
그 다음에 3번 요정이 마법을 사용하면 다음과 같은 상태로 변한다.
[3, 2, 6, 4, 1, 5]
민형이는 요정들이 M번의 마법을 쓰면서 무슨 요정이 마법을 썼는지를 시간 순서대로 기록하였다. 하지만 민형이가 기록을 찬찬히 들여다본 결과 마법 한 개분의 기록이 없다는 것을 깨달았다! 민형이가 요정들의 마나를 보는 마법을 이용하여 기록에서 빠진 마법을 쓴 요정들 중 한 마리는 찾았지만, 다른 요정이 마법을 썼는지와 언제 그 마법을 썼는지는 알 수 없다. 민형이를 도와 민형이의 기록에서 빠진 마법의 위치와 종류를 구하는 프로그램을 작성하여라.
첫 번째 줄에는 요정의 수 N과 요정이 마법을 쓰는 횟수 M이 주어진다. (2 ≤ N, M ≤ 100,000)
두 번째 줄부터 M-1개의 줄에는 요정들의 마법이 주어진다. '2 P Q'는 P번 요정과 Q번 요정이 마법을 동시에 사용한다는 의미이고 '1 P'는 P번 요정이 단독으로 마법을 사용한다는 의미이다. 요정의 번호는 1 이상 N 이하이며, 2마리의 요정이 마법을 사용한 경우 그 두 요정의 번호는 서로 다르다.
N+1번째 줄에는 요정들이 마법을 쓴 후의 요정의 번호 순서가 왼쪽에서부터 주어진다.
마지막 줄에는 기록에서 빠진 마법을 쓴 한 요정의 번호가 주어진다.
항상 답이 존재하는 입력만이 들어온다고 가정해도 좋다.
첫 번째 줄에는 민형이의 기록에서 빠진 마법의 위치 W를 출력한다. W는 기록에서 빠진 마법을 넣었을 때 그 마법의 순서 (1 이상 M 이하의 정수)를 의미한다. 두 번째 줄에는 민형이의 기록에서 빠진 마법의 종류를 출력한다. 답은 '1 P' 또는 '2 P Q' 형태로 출력한다.
답으로 가능한 경우가 여러 개일 경우 그중 아무거나 출력해도 된다.
6 3 2 2 5 1 3 3 2 6 4 1 5 4
1 1 4
5 8 2 2 4 2 1 4 2 3 5 2 4 2 2 2 3 2 1 5 2 4 3 4 5 1 2 3 3
5 2 3 4
Contest > BOJ User Contest > FunctionCup > FunctionCup 2016 F번