33406번 - Nomad Camp 다국어

문제

On summer vacation, Amir stayed at his grandmother's house, where she told him stories about how nomadic people in ancient times chose pastures for themselves:

There are only $n$ pastures, numbered from 1ドル$ to $n,ドル and $m$ roads available. Each pasture belongs to one of the four types: қыстау (winter), көктеу (spring), жайлау (summer), and күзеу (autumn).

Each pasture is initially inhabited by people, regardless of the season. When the season changes, from each pasture, people move to the nearest pasture corresponding to the new season. If there are multiple nearest pastures, they choose the pasture with the smallest number. If there is no pasture for the new season, people become sad and stop moving at all.

Now Amir wonders if it would be possible to gather all the people in one place if people could change the season of the year to any other season, as many times as they like.

입력

The first line contains a single integer $T$ (1ドル \le T \le 10^4$): the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ (1ドル \le n \le 200,ドル 1ドル \le m \le \frac{n \cdot (n - 1)}{2}$): the number of pastures and the number of roads between them.

The second line contains $n$ integers $c_1, c_2, \ldots, c_n$ (1ドル \le c_i \le 4$): the types of pastures.

Each of the next $m$ lines contains three integers, $u_i,ドル $v_i,ドル and $w_i$ (1ドル \le u_i, v_i \le n,ドル 1ドル \le w_i \le 10^5$), which mean there is a bidirectional road between pastures $u_i$ and $v_i$ that has length $w_i$.

It is guaranteed that the sum of $n$ for all test cases does not exceed 10ドル^5$.

It is guaranteed that the sum of $m$ for all test cases does not exceed 10ドル^6$.

출력

Output $T$ lines, each of which is the answer to the corresponding test case. As the answer, output "YES" if it is possible to gather everyone in one place, and "NO" otherwise.

제한

힌트