   Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
Take a Walk
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 1703 Accepted: 438

Description

A walk W in a graph G is a finite sequence

v0e1v1e2v2...vk-1ekvk

whose terms are alternately vertices and edges such that, for 1 ≤ ik, 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 v0vk 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:

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 (vi, vi)), but may contain parallel edges (i.e., 2 or more edges having the same end vertices).

Input

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.

Output

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.

Sample Input

```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) }```

Sample Output

```Yes No
No Yes
No No```

Source

[Submit]   [Go Back]   [Status]   [Discuss] Home Page Go Back To top