<PREV Problem:
NEXT>
Solved by 33 users: Anju7a, g201513, DD, Elwin, Huang_SR, tomek, wojtekt, lcosvse, dragonghy, dan, marek.cygan, gleam, zmy, JohnJones_001, fangge518, davidsun, Cheryl, pmnox, UdH-WiNGeR, Moonlight, Yagi_Arthur, RAVEman, defrager, zloy_mipt, WsemirZ, fetetriste, Kuznetsov_S, ripatti, Dest, Fat, li0n, LiuChenheng, bush.
UserDateAttemptTimeCMSC
bush17 feb 2013Ruby426.27356 
bush17 feb 2013Ruby625.09409 
WsemirZ25 mar 2009C++501.08593 
WsemirZ25 mar 2009C++301.04597 
tomek13 aug 2006C++300.72609 
tomek13 aug 2006C++200.69633 
fetetriste09 may 2009C++300.41686 
zmy28 dec 2007C++100.37714 
li0n26 aug 2011C++800.39732 
dan02 may 2007C++100.79778 
Cheryl10 jul 2008C++2800.23790 
WsemirZ25 mar 2009C++201.04798 
lcosvse16 feb 2007C++500.36831 
JohnJones_00102 jan 2008C++200.42851 
Cheryl10 jul 2008C++2700.20875 
Languages
C++
29
FPC
2
Java
1
Ruby
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Directed PS-graphs

Time limit = 5 second(s)

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

Directed PS-graph is directed 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 descriptinon is set of lines, each line contains edge description.

Edge description is two identifiers of vertices 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
  B K
  K C
  A D
is directed PS-graph.

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

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

Note that

  1. PS-graph has no cycles.
  2. PS-graph has one root (no in-edges) and one leave (no out-edges).
These conditions are necessary but not sufficient.

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

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-D
[A-D A-D]
[(A-B B-D) A-D]
[(A-B (B-C C-D)) A-D]
[(A-B ([B-C B-C] C-D)) A-D]
[(A-B ([B-C (B-K K-C)] C-D)) A-D]

Your program should output only the last line.

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


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

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

Author:
Artem Voroztsov
9 May 2006

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


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

SW soft NIX
ID = 100.26.179.196