시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 64 MB 56 14 11 32.353%

문제

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

예제 입력 2

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

예제 출력 2

5
2 3 4

힌트

출처

Contest > FunctionCup > FunctionCup 2016 F번