P15984 [PA 2026] Election Campaign / Kampania wyborcza

Local elections were held in Bajtocja. Each of the $t$ provinces elected its own governor. In each province there are several cities connected by two-way roads. During the election campaign, each political party active in the province visited some cities while touring. By convention, a party starts in some city, then moves along roads to neighboring cities a number of times (possibly $0$ times), and ends in some (possibly the same) city. During the tour, the party may pass through the same city or the same road multiple times. The parties carried out their tours in some order. Each party makes exactly one tour, and the next party can start its tour only after the previous party has finished. In every city visited by a party, the party visited all residents and convinced them to vote for it (for example, by bringing a bag of potatoes). Every visited resident is convinced, but if later a representative of another party visits the resident (for example, invites them for kebabs), the resident changes their mind. Initially, no residents are convinced to vote for anyone, but you may assume that every city is visited at least once, so its residents end up being convinced to vote for some party. Professor Bajtoni is analyzing the election results. He wants to know whether such results could have been produced by a campaign that fully follows all the rules, or whether the results clearly show that some party broke the rules or that the election was rigged. Write a program to help him answer this question for each province. Note that Professor Bajtoni does not know the order in which the parties toured. In particular, this order does not have to match the numbering order used in the statement.

The first line contains an integer $t$ ($1 \le t \le 100$), the number of provinces in Bajtocja. The following lines describe the provinces. The first line of each province description contains three integers $n, m, k$ ($1 \le n, m, k \le 10^5$), the number of cities, the number of roads, and the number of active parties in this province. The next line contains $n$ integers $a_1, \dots, a_n$ ($1 \le a_i \le k$), where $a_i$ is the number of the party that won in city $i$. Each of the next $m$ lines describes one road. The $i$-th such line contains two integers $u_i, v_i$ ($1 \le u_i, v_i \le n,\ u_i \ne v_i$), meaning there is a two-way road between cities $u_i$ and $v_i$. There is at most one road between any pair of cities. The total number of cities, the total number of roads, and the total number of parties over all provinces do not exceed $10^5$.

Output should contain $t$ lines. If the election result in the $i$-th province can be produced by a valid campaign, output the word `TAK` on the $i$-th line; otherwise output `NIE`.

### Sample Explanation In the first province, one possible scenario is: first party $1$ visits all cities, then party $2$ visits only city $2$, and then party $3$ visits only city $5$. In the second province, one possible scenario is: first parties $1$ and $3$ visit some sets of cities, and then party $2$ visits all cities. For the third province, no matter which party starts the campaign first, it is impossible to obtain the election results given in the statement. ### Scoring In all subtasks with a positive score, all provinces satisfy $m = n - 1$, and within the same province every pair of cities is connected by the existing roads (i.e., the graph is connected). Translated by ChatGPT 5