22056번 - Разбиение на команды 스페셜 저지다국어

Недавно Петя стал тренером школьной команды по баскетболу. И первая задача, с которой он столкнулся в новой роли — разбить своих подопечных на две команды: «Бурундуки» и «Капибары». В командах должно быть поровну человек.

Опросив ребят, Петя узнал, что некоторые школьники дружат друг с другом и хотят играть в одной команде, а некоторые — враждуют и, наоборот, категорически против играть вместе за одну команду. Кроме того, некоторые школьники хотят играть только в определенной команде, потому что именно в ней они тренировались в прошлом году.

Теперь Петя совсем в замешательстве и не знает, что ему делать. Помогите новому тренеру — предложите такое разбиение школьников на команды с равным числом игроков, чтобы выполнялись все вышеописанные условия, или скажите, что школьники требуют слишком много, и такого разбиения не существует.

Первая строка входных данных содержит одно число t (1 ≤ t ≤ 3000) — количество тестов. Далее следуют описания тестов. Каждый тест задается следующим образом: первая строка содержит числа n и m (1 ≤ n ≤ 3000, 0 ≤ m ≤ min(n(n − 1) ⁄ 2, 10⁵)) — количество школьников под руководством Пети и количество пар дружащих или враждующих учеников. Следующая строка теста содержит n чисел, каждое из которых равно 0, 1 или 2. Для школьника записано число 0, если ему все равно, в какой команде играть, 1, если он хочет играть в команде «Бурундуки», и 2, если он хочет играть в команде «Капибары». В следующих m строках содержится описание пожеланий пар школьников. Каждое пожелание описывается тремя числами v, u и c (1 ≤ v, u ≤ n; v ≠ u) — номера школьников и число, равное 0, если школьники v и u дружат, либо 1, если враждуют.

Гарантируется, что информация про каждую пары школьников указана не более одного раза. Также гарантируется, что сумма чисел n по всем тестам не превосходит 3000, а сумма чисел m по всем тестам не превосходит 10⁵.

Для каждого набора данных выведите «YES», если разбиение на две равные команды существует и «NO» в противном случае. Если разбиение существует, в следующей строке выведите n чисел, i-е из которых должно равняться 1 или 2 — номеру команды, в которую надо отправить i-го школьника.