描述

新的学年开始了，经过期末考的惨败，小珍在这个学期用功多了，自然也多出许多空闲的时间来。于是yuhc给她出了一道难题。

yuhc给她一个含n个结点，m条边的图。图中每两结点间的连线（路径长度）很长，小珍从一个结点寻找到另一个结点需要一定的时间，称为顺线时间。如果在yuhc给定的时间t内小珍能够从结点1出发经过x[1]，x[2]，……搜寻到x[k]，则称1，x[1]，x[2]，……，x[k]是一条合法路径。每个结点都含有一个不大于25的非负权值，每个权值看作字符串中的一位，比如字符串”7,8,9,10,1”与字符串”7,8,10,9,5”相比前者更大（逗号为字符串每位的分隔符）。现在小珍要从结点1出发，寻找一条Z路径，所谓Z路径，是指满足下面三点要求的路径：
1.路径上共有偶数个结点（包括结点1）
2.它是最长的一条偶数结点数的路径
3.同等长度的路径中，它的权值按搜索顺序组成的字符串，其字典序最小。

以上的长度是指结点数-1。

yuhc要求小珍给出图中最长的合法路径的长度，以及Z路径的权值序列。并对Z路径的权值序列作以下处理：
1.将求得的权值序列的首尾相接，形成一个环链。
2.每次将相邻的两数同时加上一个小于等于200的正整数。

那么经过有限次的第二步操作，能否使环链上所有的数字相同呢？如果能够达到，则称这个Z路径具有可加性。小珍要做的，是判断Z路径是否具有可加性，如果有，则回答”YES”，否则，回答”NO”。

由于yuhc比较空，所以他画了一个很大很大的图，因此小珍的工作量很大，自然需要你的帮忙。

数据中保证存在偶数结点的合法路径。任意一个结点只能在一条路径中出现一次。

下面的图给出了一个实例。图中，n=12，m=11，t=12。

最长合法路径为1-8-9-10-11（数字为结点序号），所以最长路径长度为5。

最长偶结点路径有两条：
1-2-3-4，对应的结点权值为10-5-2-12；
1-2-3-5，对应的结点权值为10-5-2-7；
由于10-5-2-7字典序小于10-5-2-12，所以1-2-3-5为Z路径。它的权值序列为10 5 2 7。

然后将权值序列绕成一个环链，环链及操作如下图：

所以该Z路径具有可加性。

格式

输入格式

输入包含m+2行：
第1行，用空格隔开的3个正整数，依次表示n，m，t。

第2行，共n个数，第i个数表示序号为i的结点的权值，权值为不大于25的非负整数。

第3行到第m+2行，每行给出3个用空格隔开的正整数，依次表示每一条边的两个端点的编号及它们之间的顺线时间。

对于所有数据，n<=20，t<=1E5。

输出格式

输出包含3行：
第1行为图中最长的合法路径的长度。

第2行为Z路径的结点的权值，按搜索顺序输出，之间用一个空格隔开。

第3行为环链可加性判定结果，输出YES或NO。

样例1

样例输入1

12 11 12
10 5 2 12 7 1 6 8 3 2 5 8
1 2 3
2 3 6
3 4 2
3 5 1
5 6 3
6 7 2
1 8 4
8 9 2
9 10 5
10 11 1
11 12 6

样例输出1

5
10 5 2 7
YES

限制

所有数据时限为1s

提示

1.环链处理时不要进行取模。

2.为了简化题目：不必输出环链处理步骤和最终环链上的数字。

3.图中所有的边都是单向的。

4.数据保证仅存在一条Z路径。

来源

jszx