레이스

랠리 경주에 자동차 $N$대가 참가했다. 경기가 끝난 뒤 방송 담당자들은 촬영한 영상을 편집하려고 한다. 그들이 가장 중요하게 여기는 것은 경주 중 일어난 모든 추월 장면을 순서대로 보여 주는 것이다. 그런데 편집을 하던 중 담당자들은 순서가 뒤엉켜 버렸다. 자신들이 편집한 추월 순서가 실제로 가능한 순서인지 어떻게 확인할 수 있을까?

자동차들의 출발 순서(맨 앞에서 맨 뒤까지의 초기 순위)와 추월 기록이 순서대로 주어진다. 경주는 한 줄로만 지나갈 수 있는 좁은 도로에서 진행되므로, 어떤 자동차는 자기 바로 앞에 있는 자동차만 추월할 수 있다. 추월이 일어나면 두 자동차의 순위가 서로 뒤바뀐다. 즉 기록 $(a, b)$는 '자동차 $a$가 바로 앞에 있던 자동차 $b$를 추월했다'는 뜻이며, 이 추월은 추월 직전에 $a$가 $b$의 바로 뒤에 있을 때에만 가능하다.

주어진 추월 기록이 이 순서대로 실제로 일어날 수 있었는지 판별하는 프로그램을 작성하시오.

첫째 줄에 자동차의 수 $N$이 주어진다. 둘째 줄에는 자동차 번호가 출발한 순서대로, 즉 가장 먼저 출발한(맨 앞에 있는) 자동차부터 차례로 주어진다. 모든 자동차 번호는 $1$ 이상 $N$ 이하의 서로 다른 정수이다.

셋째 줄에는 추월 횟수 $L$이 주어진다. 이어지는 $L$개의 줄에는 각각 정수 쌍 $a$ $b$가 주어지며, 이는 자동차 $a$가 자동차 $b$를 추월했음을 뜻한다. 이 쌍들은 담당자들이 편집한 기록의 순서대로 주어진다. 경주 중 적어도 한 번의 추월이 일어났음이 보장된다.

주어진 기록대로 경주가 진행될 수 있었다면, 첫째 줄에 TAIP를 출력하고 둘째 줄에 자동차들의 최종 순서를 입력의 둘째 줄과 같은 형식(맨 앞부터 맨 뒤까지 공백으로 구분)으로 출력한다.

담당자들이 편집 과정에서 실수를 했다면, 즉 어떤 추월이 그 시점에 불가능했다면, 첫째 줄에 NE를 출력하고 둘째 줄에 불가능한 추월의 번호를 출력한다. 추월 번호는 $1$부터 세며, 불가능한 추월이 여러 개라면 그중 가장 먼저 나오는 것의 번호를 출력한다.

• $1 < N \le 1000$
• $1 \le L \le 100000$