程序设计基础一的上机考试题目已在OJ开放,大家可以补题了。

Problem 2054. -- 死宅的旅行

2054: 死宅的旅行

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 11  Accepted: 5
[Submit][Status][Web Board]

Description

ACM国是一个由V个城市(城市编号从1V组成国家,城市之间有一些双向的公路(每两个城市之间最多只有一条公路直接相连)。

生活在城市1pjl是一个死宅,他非常讨厌外出,但是有的时候他出于一些不可告人的原因要前往城市V,于是他决定到达目的地之后原路返回。由于他非常讨厌外出,所以他想要走的路程最少,而且由于他忙于做一些不可描述的事情,他没有时间去找那条最短的路径,于是他找到了你,让你帮忙找到一条满足要求的路径。

以上是Yasola原本准备出的题目,不过他觉得这么简单的题目你一定会写,而且由于可能出现多条满足要求的路径,要判断答案的正确性需要一个有点麻烦special judge程序,可是Yasola最近忙于划水,于是决定把写special judge的任务交给你。

Input

多组测试数据,每组测试数据第一行两个数字V(1<=V<=100)E(0<=E<=10000)分别表示城市的数目和城市之间的双向路的数目,当VE都为0时表示输入结束。接下来E行,每行三个整数u,v,c(1<=u,v<=V,0<=c<=100)分别表示一条路的两个端点和距离。下一行一个正整数N表示待判断答案中要走的路的数目,接下来N(0<=N<=100)行,第i行输入两个正整数a,b(1<=a,b<=V)表示路径的第i步为从城市a走到城市b

Output

每组测试数据输出一行,如果待检查答案正确,输出Yes”,否则输出No”

Sample Input

4 5
1 2 1
1 3 1
2 4 1
4 3 2
1 4 4
2
1 2
2 4
5 6
1 2 2
1 4 3
2 3 1
2 5 4
2 4 1
4 5 2
2
1 2
2 5
0 0

Sample Output

Yes
No

HINT


真正的Special Judge程序和本题要求有所不同,请按照本题要求写程序。

Author

Yasola

[Submit][Status][Web Board]