A walk W in a graph G is a finite sequence
whose terms are alternately vertices and edges such that, for 1 ≤ i ≤ k, the edge ei has end vertices vi-1 and vi. If the edges e1, e2, ... , ek of the walk are distinct, then W is called a trail. A trail with v0 ≠ vk is an open trail.
If v0 = vk, then W is a closed walk. A tour of G is a closed walk of G that includes every edge of G at least once.
Write a program that determines whether for a graph G:
where graph G is undirected, has at least 2 edges, has no self-loops (i.e., edges (vi, vi)), but may contain parallel edges (i.e., 2 or more edges having the same end vertices).
The input file consists of several test cases, each with a case number, the set of vertices in a graph, and the set of edges in the graph, as shown in the samples. Assume the vertices are single letters only.
For each of the test cases, output "Yes" if the graph has at least one open trail that includes every edge of the graph, and "No", if not; and output "Yes" if the graph has at least one tour that includes every edge of the graph exactly once, and "No" if not.
Case 1: { a, b, c, d, e } { (a,b), (b,c), (c,d), (d,a), (b,e), (c,e) }
Case 2: { a, b, c, d, e } { (a,b), (a,c), (b,e), (b,d), (b,c), (d,c), (d,e), (d,e), (e,c) }
Case 3: { A, B, c, d } { (A,B), (c,d) }
Yes No No Yes No No