공항 에어쇼

항공사 Flying Bugs는 광고 캠페인의 일부로 에어쇼를 준비하고 있습니다. 쇼는 1번부터 N번까지 번호가 매겨진 N개의 활주로를 갖춘 회사 공항에서 열리며, 두 곡예비행팀이 동시에 공연합니다. 각 공연은 정해진 프로그램을 따르며, 시각적 효과를 유지하기 위해 비행기들은 정해진 순서대로 특정 활주로에서 이륙하고 착륙해야 합니다.

공항의 보안 시스템은 어떤 활주로가 사용 중인지 추적하며, 활주로가 사용 중인 동안에는 다른 어떤 비행기도 그 활주로에 진입하지 못하게 합니다. 각 공연은 특정 활주로에 대한 예약(RES) 요청과 해제(REL) 요청의 수열로 보안팀에 전달됩니다. 이 요청들이 실제로 언제 도착할지는 미리 예측할 수 없습니다. 관계자들은 두 공연의 요청이 서로 엇갈려 진행되다가 어느 순간 두 공연 모두 자신의 활주로 사용 순서를 어기지 않고서는 더 이상 진행할 수 없게 되는 경우가 존재하는지 알고 싶어 합니다.

각 공연 자체의 요청 수열은 다음 조건을 만족합니다.

• 이미 예약된 활주로는 먼저 해제되기 전에는 다시 예약되지 않는다,
• 현재 예약되어 있고 아직 해제되지 않은 활주로만 해제할 수 있다,
• 예약된 모든 활주로는 공연이 끝나기 전에 해제된다.

어떤 공연이 필요로 하는 활주로가 현재 다른 공연에 의해 예약되어 있다면, 그 공연은 상대가 해당 활주로를 해제할 때까지 기다릴 수 있습니다(상대 공연은 그동안 여러 활주로를 예약하고 해제하다가 결국 요청된 활주로를 해제할 수 있습니다).

한 공연이 상대가 점유한 활주로를 요청하는 동시에, 자신은 상대가 요청하는 활주로를 점유하고 있으면 공항은 막힙니다. 이 경우 두 공연 모두 정해진 순서를 어기지 않고서는 진행할 수 없습니다. 여러분의 임무는 이러한 막힘이 발생하는 진행 순서가 존재하는지 판별하는 것뿐이며, 막힘을 피하도록 공연 일정을 짤 필요는 없습니다.

첫째 줄에는 공항의 활주로 수를 나타내는 정수 N (1 ≤ N ≤ 1000)이 주어집니다. 이어서 각 공연을 설명하는 두 블록이 주어집니다. 각 블록의 첫 줄에는 그 공연에서 이루어지는 예약과 해제 요청의 수를 나타내는 짝수 L (2 ≤ L ≤ 5000)이 하나 주어집니다. 이어지는 L개의 줄 각각에는 3글자 문자열 RES 또는 REL과 정수 A (1 ≤ A ≤ N)가 공백 하나로 구분되어 주어집니다. RES A는 활주로 A의 예약을, REL A는 활주로 A의 해제를 요청합니다.

두 요청 수열의 모든 가능한 진행 순서에서 두 공연 모두 공항을 막지 않고 끝난다면, 다음을 정확히 출력합니다.

The performances will always finish.

그렇지 않다면 막힌 상태에 도달하는 진행 순서가 하나 이상 존재합니다. 그러한 진행 순서 하나를, 구분자 없이 이어 쓴 숫자 1과 2의 수열로 출력합니다. 수열을 왼쪽에서 오른쪽으로 읽을 때 각 숫자는 다음 대기 요청을 수행하는 공연을 가리킵니다. 첫 숫자가 가리키는 공연이 자신의 첫 대기 요청을 수행하고, 다음 숫자가 가리키는 공연이 자신의 다음 대기 요청을 수행하는 식입니다. 이 수열은 매 단계에서 유효해야 하며(각 활주로는 한 순간에 최대 한 공연만 예약함), 정확히 막힌 상태에서 멈춰야 합니다. 즉 공연 1의 다음 대기 요청은 공연 2가 점유한 활주로의 예약을 요구하고, 공연 2의 다음 대기 요청은 공연 1이 점유한 활주로의 예약을 요구해야 합니다.

막힌 상태에 도달하는 진행 순서가 여러 개일 수 있으므로 사전순으로 가장 작은 수열을 출력합니다. 두 수열을 문자 1과 2로 이루어진 문자열로 보고 비교하며(1 < 2), 왼쪽부터 훑어 처음으로 달라지는 자리에서 더 작은 숫자를 가진 수열이 더 작습니다.