Гра#825

Гра

5 секунд

64 мегабайти

Дуже складна

Дитина намалювала $N$ ( $N \leq 100$ N \le 100) пронумерованих кружечків різних кольорів. Вона з'єднала деякі кружечки кольоровими стрілками. Кожна пара кружечків могла бути з'єднана довільною кількістю стрілок будь-якого кольору. Кожному кольору присвоєно номер, що не перевищує $100$ .

Перед початком гри дитина поклала одну фішку на кружечок номер $L$ , а другу — на інший кружечок номер $K$ . Фініш — інший кружечок номер $Q$ . Далі гра відбувається за такими правилами:

Фішку можна рухати по стрілці, що виходить з її кружечка, якщо колір стрілки збігається з кольором кружечка, на якому знаходиться інша фішка.
Дві фішки ніколи не можуть знаходитися на одному кружечку одночасно.
Порядок ходів вільний (тобто фішки не обов'язково рухати по черзі).
Гра закінчується, коли будь-яка з двох фішок досягає кружечка з номером $Q$ .

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

Вхідні дані

Перший рядок вхідного файлу містить числа $N$ , $L$ , $K$ , $Q$ , розділені пробілами. Другий рядок містить $N$ цілих чисел $c_{1}$ c_1, $c_{2}$ c_2, $\dots$ , $c_{N}$ c_N, розділених пробілами, де $c_{i}$ c_i — це колір кружечка номер $i$ . Третій рядок містить одне число $M$ ( $0 \leq M \leq 10000$ 0 \le M \le 10000) — загальна кількість стрілок. Кожен із наступних $M$ рядків описує одну стрілку трьома цілими числами $A_{j}$ A_j, $B_{j}$ B_j, $C_{j}$ C_j: $A_{j}$ A_j і $B_{j}$ B_j — номери кружечків (стрілка йде від $A_{j}$ A_j до $B_{j}$ B_j), а $C_{j}$ C_j — колір стрілки.

Вихідні дані

Перший рядок вихідного файлу повинен містити YES, якщо гру можна завершити, і NO в іншому випадку. Якщо відповідь YES, другий рядок має містити одне число — мінімальну кількість ходів для завершення гри.

Приклади

Приклад 1