Local government elections have taken place in Byteotia. Each of the $t$ provinces has elected its own governor. In each province, there is a certain number of cities connected by bidirectional roads. As part of the campaign, each of the parties operating in a given province visited a certain number of cities during a tour. According to tradition, a party starts its route in a certain city, travels a number of times (possibly 0) to a connected city, and ends in a certain (possibly the same) city, potentially passing through the same city or road multiple times.

The parties conducted their tours in a certain order, where each party performed only one tour, and the next party's tour could only begin after the previous one had finished. In any city that a party passed through, it visited all the residents and convinced them to vote for it (for example, by bringing them a sack of potatoes). Every visited resident was convinced, but changed their mind if a representative of another party visited them later (and, for example, invited them for a kebab).

Initially, none of the residents were convinced to vote for anyone, but you can assume that each city was visited at least once and its residents were convinced to vote for one of the parties.

Professor Bajtoni is analyzing the election results and wonders if it is possible to obtain them after a campaign conducted according to all the rules, or if they clearly indicate that some party did not follow the rules or that the election was rigged.

Write a program that will help him answer this question for each of the provinces.

Note that Professor Bajtoni does not know the order in which the parties conducted their tours — in particular, this order does not have to be consistent with the numbering in the problem description.

Input

The first line of input contains a single integer $t$ ($1 \le t \le 100$) denoting the number of provinces in Byteotia.

The following lines contain descriptions of the provinces. The first line of a province description contains three integers $n, m, k$ ($1 \le n, m, k \le 10^5$) denoting the number of cities, the number of roads, and the number of parties operating in the given province, respectively.

The next line contains a sequence of $n$ integers $a_1, \dots, a_n$ ($1 \le a_i \le k$); the number $a_i$ denotes the number of the party that won in the $i$-th city.

The next $m$ lines contain descriptions of the roads in the province: the $i$-th of these contains two integers $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$) denoting a bidirectional road between cities $u_i$ and $v_i$. There is at most one road between any pair of cities.

The total number of cities across all provinces, the total number of all roads, and the total number of all parties do not exceed $10^5$.

Output

Output $t$ lines; the $i$-th line should contain the word TAK if the election results in the $i$-th province could have been obtained as a result of the campaign, or NIE otherwise.

Examples

Input 1

3
5 5 3
1 2 1 1 3
1 2
2 3
3 4
4 5
5 1
4 3 3
2 2 2 2
1 2
1 3
1 4
4 3 2
1 2 1 2
1 2
2 3
3 4

Output 1

TAK
TAK
NIE

Note 1

In the first province, a scenario is possible where party 1 visited all cities first, then party 2 visited only city number 2, and then party 3 visited only city number 5.

In the second, a scenario is possible where parties 1 and 3 visited a certain set of cities first, and then party number 2 visited all cities.

In the case of the third province, regardless of which party conducted its campaign first, it is not possible to obtain the given election result.

Subtasks

In at least one test group, all provinces satisfy the condition $m = n - 1$ and it is possible to travel between any pair of cities within a single province using the existing roads.