题目描述

一个孩子画了$N（N≤100）$个不同颜色的编号圆圈。他用彩色有向线段连接了其中一些圆圈。任意两个圆圈之间可能有任意数量、任意颜色的线段相连。每个颜色（圆圈颜色或线段颜色）都被赋予一个唯一的正整数编号（不超过$100$）。

游戏开始时，孩子首先选择三个不同的整数$L、K、Q（1≤L,K,Q≤N）$。然后他将一个棋子放在圆圈$L$，另一个放在圆圈$K$，并按照以下规则移动棋子：
$1$. 当线段颜色与另一个棋子所在圆圈的颜色相同时，该棋子可以沿此线段移动。
$2$. 棋子只能沿线段的方向移动（所有线段均为有向线段）。
$3$. 两个棋子不能同时位于同一个圆圈中。
$4$. 移动顺序自由（无需交替移动棋子）。
$5$. 当任意一个棋子到达终点圆圈$Q$时，游戏结束。

请编写程序找出该游戏的最短解决方案（即最少移动次数），若存在的话。

输入

输入文件的第一行包含整数$N、L、K、Q$（由空格分隔）。第二行包含$N$个整数$c₁, c₂, ..., cₙ$（由空格分隔），表示圆圈$i$的颜色。第三行是一个整数$M（0≤M≤10000）$，表示线段总数。接下来M行描述每条有向线段，每行包含三个整数$Aⱼ、Bⱼ、Cⱼ$（由空格分隔），表示线段方向为$Aⱼ→Bⱼ$，颜色为$Cⱼ$。

输出

若游戏可以结束，输出第一行应为"$YES$"，否则为"$NO$"。若答案为"$YES$"，第二行输出一个整数，表示完成游戏所需的最少移动次数。

输入示例 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  

输出示例 1

YES  
3  

来源

Northeastern Europe 1997