Игра
Игра
Ребенок нарисовал N (N ≤ 100) пронумерованных кружков различного цвета. Он соединил некоторые кружки цветными стрелками. Каждая пара кружков при этом могла оказаться соединенной любым количеством стрелок любого цвета. Дадим каждому цвету свой номер, не превосходящий 100.
Перед началом игры ребенок положил одну фишку на кружок номер L, а вторую — на несовпадающий с первым кружок номер K. Финишной считается несовпадающая с ними клетка с номером Q. Затем начинается игра по следующим правилам:
Фишку можно передвинуть по стрелке, идущей из ее кружка, если цвет стрелки совпадает с цветом кружка, на котором расположена другая фишка.
Две фишки никогда не могут находиться на одном и том же кружке в одно и то же время.
Порядок ходов свободный (т.е. нет необходимости передвигать фишки по очереди).
Игра заканчивается, когда любая из двух фишек достигнет кружка номер Q.
Вы должны написать программу, которая будет определять минимальное число ходов, за которое можно закончить игру, если ее окончание существует.
Input data
Первая строка входного файла содержит числа N, L, K, Q, разделенные пробелами. Вторая строка состоит из N целых чисел c_1, c_2, ... , c_N, разделенных пробелами, в таком порядке, что c_i означает цвет кружка номер i. Третья строка состоит из одного числа M (0 ≤ M ≤ 10000), обозначающего общее число стрелок. Каждая из следующих M строк описывает одну из стрелок. Каждая стрелка описывается тремя целыми числами A_j, B_j, C_j, разделенных пробелами, где A_j и B_j— номера кружков (стрелка направлена от кружка A_j к B_j, а C_j обозначает цвет стрелки.
Output data
Первая строка выходного файла должна содержать слово "YES", если игра может закончиться и "NO" в противном случае. Если ответ на этот вопрос —"YES", то во второй строке входного файла должно содержаться одно число — минимальное количество ходов, которое нужно сделать для окончания игры.
Examples
5 3 4 1 2 3 2 1 4 8 2 1 2 4 1 5 4 5 2 5 1 3 3 2 2 3 2 4 5 3 1 3 5 1
YES 3