에디터 전쟁
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- EDITORWARS
- 4000ms
- 65536kb
- 2608
- 585 (22%)
-
- 출처
- 분류
문제
에디터 전쟁은 가장 유명한 자유 소프트웨어 텍스트 편집기인 vi와 Emacs 중 어느 쪽이 더 우월한가를 놓고 인터넷에서 자주 벌어지는 논쟁을 말합니다. 이 논쟁에 참여하는 사람들은 서로 자신이 사용하는 편집기의 장점을 찬양하고 (“vi는 동작도 빠르고, 빠른 편집을 가능하게 한다고”, “Emacs는 LISP을 통해 확장 가능하다고”) 다른 편집기를 헐뜯곤 (“vi-vi-vi는 666이잖아! vi는 악마의 편집기야”, “Emacs는 좋은 운영 체제지. 좋은 편집기가 없는 것만 빼면 완벽해”) 합니다.
모든 회원들이 vi 혹은 Emacs를 사용하는 프로그래밍 동호회에서 연말 파티를 개최하려 합니다. 서로 다른 편집기를 사용하는 사람들이 파티에 함께 참가하면 싸움이 나기 때문에 vi를 사용하는 사람들만 오는 파티, Emacs를 사용하는 사람들만 오는 파티를 따로 하기로 했습니다. 이를 위해 지금까지 모든 회원들이 쓴 댓글을 모아 이들을 두 종류로 분류했습니다.
- 상호 인정: 이 유형의 댓글은 댓글을 쓴 사람과 원글을 쓴 사람이 같은 편집기를 쓴다는 사실을 의미합니다. 예로 “아이고 이런 편집기를 쓰시다니 뭘 아는 분이네” 혹은 “역시 편집기는 xxx가 짱이죠” 등이 있겠지요.
- 상호 비방: 이 유형의 댓글은 댓글을 쓴 사람과 원글을 쓴 사람이 다른 편집기를 쓴다는 사실을 의미합니다. 예로 “그런 편집기 쓰면 손가락에 마비가 올 것 같네요” 혹은 “훠어이 악마의 편집기는 물러가라” 등이 있겠지요.
이것만으로는 물론 각 사용자가 어떤 편집기를 쓰는지는 알 수 없지만, 우선 서둘러 장소를 예약해야 하기 때문에 이 정보만으로 파티에 올 수 있는 최대 인원을 알아야 합니다. 댓글 정보가 주어질 때 이 댓글 정보 중 모순되는 것은 없는지 확인하고, 모순되는 것이 없을 때 한 파티의 가능한 최대 인원을 계산하는 프로그램을 작성하세요.
입력
입력의 첫 줄에는 테스트 케이스의 수 C (1≤C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 회원의 수 N (1≤N≤10000)과 분석한 댓글의 개수 M (1≤M≤100000)이 주어집니다. 각 회원은 0에서 N - 1 범위의 숫자로 표현됩니다.
그 후 M줄에 하나씩 각 댓글의 정보가 주어집니다. 각 댓글은 상호 인정, 혹은 상호 비방 댓글입니다. 상호 인정 댓글은 “ACK a b”(0≤a, b<N) 형태로 주어지며 상호 비방 댓글은 “DIS a b” 형태로 주어집니다.
출력
각 테스트 케이스마다 한 줄을 출력합니다.
- ᆞ댓글에 주어진 정보 중 모순이 없는 경우 한 파티에 올 수 있는 사람의 최대 수를 “MAX PARTY SIZE IS x”의 형태로 출력합니다.
- ᆞ댓글들에 주어진 정보 중 모순이 있는 경우, 모순이 처음으로 발생하는 댓글이 몇 번인지를 “CONTRADICTION AT i” 형태로 출력합니다. 댓글의 번호는 입력에 주어진 순서대로 1부터 시작한다고 합시다.
예제 입력
4 4 4 ACK 0 1 ACK 1 2 DIS 1 3 ACK 2 0 100 4 ACK 0 1 ACK 1 2 ACK 2 3 ACK 3 4 3 3 ACK 0 1 ACK 1 2 DIS 2 0 8 6 DIS 0 1 ACK 1 2 ACK 1 4 DIS 4 3 DIS 5 6 ACK 5 7
예제 출력
MAX PARTY SIZE IS 3 MAX PARTY SIZE IS 100 CONTRADICTION AT 3 MAX PARTY SIZE IS 5
노트
