eolymp
bolt
Try our new interface for solving problems
Problems

Игра

Игра

Time limit 5 seconds
Memory limit 64 MiB

Ребенок нарисовал N (N100) пронумерованных кружков различного цвета. Он соединил некоторые кружки цветными стрелками. Каждая пара кружков при этом могла оказаться соединенной любым количеством стрелок любого цвета. Дадим каждому цвету свой номер, не превосходящий 100.

Перед началом игры ребенок положил одну фишку на кружок номер L, а вторую — на несовпадающий с первым кружок номер K. Финишной считается несовпадающая с ними клетка с номером Q. Затем начинается игра по следующим правилам:

  • Фишку можно передвинуть по стрелке, идущей из ее кружка, если цвет стрелки совпадает с цветом кружка, на котором расположена другая фишка.

  • Две фишки никогда не могут находиться на одном и том же кружке в одно и то же время.

  • Порядок ходов свободный (т.е. нет необходимости передвигать фишки по очереди).

  • Игра заканчивается, когда любая из двух фишек достигнет кружка номер Q.

Вы должны написать программу, которая будет определять минимальное число ходов, за которое можно закончить игру, если ее окончание существует.

Input data

Первая строка входного файла содержит числа N, L, K, Q, разделенные пробелами. Вторая строка состоит из N целых чисел c_1, c_2, ... , c_N, разделенных пробелами, в таком порядке, что c_i означает цвет кружка номер i. Третья строка состоит из одного числа M (0M10000), обозначающего общее число стрелок. Каждая из следующих M строк описывает одну из стрелок. Каждая стрелка описывается тремя целыми числами A_j, B_j, C_j, разделенных пробелами, где A_j и B_j— номера кружков (стрелка направлена от кружка A_j к B_j, а C_j обозначает цвет стрелки.

Output data

Первая строка выходного файла должна содержать слово "YES", если игра может закончиться и "NO" в противном случае. Если ответ на этот вопрос —"YES", то во второй строке входного файла должно содержаться одно число — минимальное количество ходов, которое нужно сделать для окончания игры.

Examples

Input example #1
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
Output example #1
YES
3