<PREV Problem:
NEXT>
Solved by 26 users: tomek, wojtekt, Jacob, DD, dragonghy, dan, marek.cygan, asp, zmy, JohnJones_001, Red75, fangge518, davidsun, Cheryl, mazahaka, gleam, zloy_mipt, pmnox, RAVEman, defrager, UdH-WiNGeR, WsemirZ, ripatti, Dest, Fat, bush.
UserDateAttemptTimeCMSC
bush17 feb 2013Ruby344.51516 
tomek13 aug 2006C++100.97523 
bush17 feb 2013Ruby443.80524 
mazahaka16 sep 2008C++101.49646 
Jacob14 oct 2006C++302.35650 
Jacob14 oct 2006C++202.35652 
WsemirZ29 mar 2009C++601.46655 
dan02 may 2007C++201.27764 
ripatti25 jun 2010C++301.14785 
zmy29 dec 2007C++300.66893 
pmnox04 feb 2009C++100.31949 
defrager15 mar 2009C++400.68966 
Languages
C++
23
Java
1
Ruby
1
FPC
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Undirected PS-graphs

Time limit = 5 second(s)

Your program should check if graph is undirected PS-graph.

Undirected PS-graph is undirected graph (or multigraph — graph with multiple edges) that can be produced from one-edge graph by the applying operations:

1) double edge : from "A-B" make two edges "A-B" and "A-B".

2) split edge: from "A-B" make two edges "A-C" and "C-B", where C is new vertex.

Graph description is set of lines, each line contains edge description.

Edge description is two vertex identifiers delimited by space. Vertex identifier is nonempty word from B*, B={A..Z, a..z, 0..9}. Word length is less than 11 letters.

Graph G

  A B
  B C
  C D
  A D
  A C
is undirected PS-graph.

It can be produced from edge "A-C" in the following way:

<i>PS</i>-graph sample.

Note that

  1. undirected PS-graph can have cycles.
  2. What are the two vertices of the starting edge A-B is unknown
  3. "A-B" and "B-A" stands for the same edge.

Input. Graph description. Number of edges is less than 21000.

Output. First line should contain YES or NO depending on whether the input graph is PS-graph. If YES, then next line should have description of operation sequence.

When doubling the edge "A-B" one writes

[A-B A-B]

When spliting the edge "A-B" by vertex C one writes

(A-C C-B)

So for the given sample graph G output can be the following:

A-C
[A-C A-C]
[A-C [A-C A-C]]
[A-C [(A-B B-C) A-C]]
[A-C [(A-B B-C) (A-D D-C)]]

Your program should output only the last line. Note that here order of vertices in edge description does matter.

Input#1
A B
B C
C D
A D
C A
Output#1
YES
[A-C [(A-B B-C) (A-D D-C)]]


Input#2
A B
B C
A D
D C
D B
D A
Output#2
YES
[D-C ([D-B ([D-A D-A] A-B)] B-C)]


Input#3
A B
B C
A D
D C
D B
D A
A C
Output#3
NO

Author:
Artem Voroztsov
9 May 2006

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 180ms

SW soft NIX
ID = 3.226.248.180