관료제

시간 제한3초메모리 제한256 MB

요약
직접법과 취소법으로 이루어진 사슬 구조에서, 어떤 활성 법도 그 법을 취소하지 않을 때만 활성으로 간주하여 최종적으로 활성 상태인 법들을 구하는 문제입니다.
난이도

보통10점 중 5점

유형
시뮬레이션, 구현, 배열
정답자
아직 제출이 없습니다

문제

먼 옛날, 어느 머나먼 왕국에서 왕은 나라의 모든 법을 기록으로 남기기로 했다. 그때부터 새로운 법이 통과될 때마다 그에 해당하는 기록이 법률 문서고에 추가되었다.

여러 세기가 지난 뒤, 학자들은 이 왕국에 오직 두 종류의 법만 존재했다는 사실을 알아냈다:

  • 새로운 규범을 세우는 직접법;
  • 이전의 법 하나를 취소하는 취소법.

어떤 법은 그 법을 취소하는 활성 법이 하나도 없을 때, 그리고 오직 그때에만 활성 상태로 간주된다.

어떤 법들이 여전히 활성 상태인지 알아내는 프로그램을 작성하라.

입력

첫째 줄에는 통과된 법의 개수를 나타내는 정수 1≤n≤100 0001 \le n \le 100\,000가 주어진다.

이어지는 nn개의 줄에는 각각 법 하나가 다음 두 형식 중 하나로 주어진다:

  • declare --- 직접법이 통과되었음을 뜻한다.
  • cancel ii --- 이 취소법이 이전의 법 중 하나인 ii번 법을 취소함을 뜻한다.

법은 등장하는 순서대로 1번부터 번호가 매겨진다.

출력

첫째 줄에 활성 상태인 법의 개수를 출력한다. 둘째 줄에는 활성 상태인 법들의 번호를 오름차순으로, 하나의 공백으로 구분하여 출력한다.

예제3

  1. 예제 1

    입력
    5
    declare
    cancel 1
    declare
    cancel 2
    cancel 3
    
    예상 출력
    3
    1 4 5
    
  2. 예제 2

    입력
    1
    declare
    
    예상 출력
    1
    1
    
  3. 예제 3

    입력
    2
    declare
    cancel 1
    
    예상 출력
    1
    2