Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Take a Walk
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1455Accepted: 319

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


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator