|Online Judge||Problem Set||Authors||Online Contests||User|
A child has drawn N (N<=100) numbered circles of different colors. He has connected some of the circles by colored oriented line segments. Every pair of circles may have any number of segments, with any colors, connecting them. Each color (either circle color or segment color) is assigned its own unique positive integer number not greater than 100.
Starting the game the child first of all chooses three different integers L, K and Q within the range between 1 and N. Then he places one pawn into the circle number L and another one into the circle number K, whereupon he begins to move them using the following rules:
You are to write a program to find out the shortest (i.e. containing a minimal number of moves) solution for this game, if it exists.
The first line of the input file contains integers N, L, K, Q separated by spaces. The second line consists of N integers c1, c2, ... , cn, separated by spaces, in the given order, where ci is the color of the circle number i. The third line consists of a single integer M (0<=M<=10000) denoting the total number of segments. Then follow M lines, each containing a description of one oriented segment. Each segment is described by three integer numbers Aj, Bj, Cj, separated by spaces, where A and B are the numbers of the circles connected by the j-th segment with direction from Aj to Bj, and Cj represents the color of this segment.
The first line of the output file should contain the word "YES", if the game can come to the end, and "NO" otherwise (without quotes). If the answer is "YES", the second line of the output should contain just a single integer - the minimum number of the moves the child should make to finish the game.
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
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator