The Race

Time limit1sMemory limit1024 MB

Summary

Given the starting order of cars and a recorded list of adjacent overtakes, verify the sequence is valid and print the final order or the first impossible overtake.

Level: Medium4 of 10
Topics: Simulation, Array, Implementation, Linked list
Solved: No attempts yet

Problem

$N$ cars took part in a rally race. After the race ends, the broadcast crew wants to edit all of the footage they filmed. The most important thing to them is to show every overtake that happened during the race, in order. While editing, however, the crew got the sequence mixed up: how can they tell whether the order of overtakes they assembled could really have happened?

You are given the cars' starting order (their initial ranking from the very front to the very back) and the list of overtakes in the order recorded. The race runs on a narrow, single-file road, so a car can only overtake the car directly in front of it. When an overtake happens, the two cars swap ranks. That is, a record $(a, b)$ means "car $a$ overtook the car $b$ that was directly ahead of it," and this overtake is possible only if, just before it, $a$ is immediately behind $b$ .

Write a program that decides whether the given sequence of overtakes could really have occurred in that order.

Input

The first line contains the number of cars $N$ . The second line lists the car numbers in starting order, that is, from the car that started first (at the very front) to the last. All car numbers are distinct integers from $1$ to $N$ .

The next line contains the number of overtakes $L$ . Each of the following $L$ lines contains a pair of integers $a$ $b$ , meaning that car $a$ overtook car $b$ . The pairs are given in the order the crew assembled them. It is guaranteed that at least one overtake happened during the race.

Output

If the race could have proceeded exactly as recorded, print TAIP on the first line and, on the second line, the final order of the cars in the same format as the input's second line (from the very front to the very back, separated by spaces).

If the crew made a mistake, that is, some overtake was impossible at that moment, print NE on the first line and, on the second line, the index of that overtake. Overtakes are numbered from $1$ ; if several are impossible, print the index of the first such overtake.

Constraints

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

Examples2

Example 1
Input
```
3
1 2 3
3
3 2
3 1
2 1
```
Expected output
```
TAIP
3 2 1
```
Example 2
Input
```
3
1 2 3
3
3 2
2 1
3 1
```
Expected output
```
NE
2
```