Bachelor Party

Bajtazar is about to change his marital status, and his loyal friends want to make his last days of freedom unforgettable.

Byteotia has $n$ cities, numbered from $0$ to $n-1$. Some pairs of cities are joined by a two-way road, but most roads are under repair. Exactly enough roads remain so that between every pair of cities there is exactly one route made of roads. In other words, the open roads form a tree.

Bajtazar's friends have also bought $p$ flight tickets. Each ticket allows a single flight, taken at any moment, from some city $a$ to some city $b$ (one way only, never from $b$ back to $a$).

Bajtazar wants to start his journey in a fixed city $s$ and finish it in a fixed city $t$. Along the way he may use any roads and must use all of his tickets, in any order he likes. Unfortunately, once he leaves a city he can never return to it, so no city may be visited more than once during the whole trip.

Decide whether a journey satisfying all of these conditions exists.

The first line contains the number of test cases $T$. Then $T$ test cases follow, each in the form below.

The first line of a test case contains three integers $n$, $m$ and $p$ ($2 \le n \le 100\,000$, $1 \le m \le 1\,000\,000$, $1 \le p \le 1\,000\,000$): the number of cities, the number of open roads, and the number of flight tickets. The open roads always form a tree, so $m = n - 1$.

The second line contains two integers $s$ and $t$ ($0 \le s, t \le n-1$): the start city and the end city.

The next $m$ lines describe the roads, one per line. Each road is given by two integers $a_i$ and $b_i$ ($0 \le a_i, b_i \le n-1$, $a_i \ne b_i$), meaning there is a two-way road between cities $a_i$ and $b_i$.

The next $p$ lines describe the tickets, one per line. Each ticket is given by two integers $c_i$ and $d_i$ ($0 \le c_i, d_i \le n-1$, $c_i \ne d_i$), meaning Bajtazar owns a ticket for a flight from city $c_i$ to city $d_i$.

For each test case print a single line containing the word TAK if the journey Bajtazar wants can be arranged, or NIE if it is impossible. Here TAK means yes and NIE means no.