Take a Walk

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 e_i has end vertices v_i-1 and v_i. If the edges e₁, e₂, ... , e_k of the walk are distinct, then W is called a trail. A trail with v₀ ≠ v_k is an open trail.

If v₀ = v_k, 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:

1. there exists an open trail that includes every edge of G, or not; and
2. there exists a tour that includes every edge of G exactly once, or not

where graph G is undirected, has at least 2 edges, has no self-loops (i.e., edges (v_i, v_i)), 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