Draw a network of nodes There is a network of up to 26 nodes (named A to Z or a to z as per your wish). Every pair of nodes may be connected or disconnected. A node may be connected to at most 4 other nodes. Your task is to draw the network in a 2D diagram. Input will be given such that this task is possible (see more constraints in output section).


Format

Input


Pairs of letters (A to Z or a to z as per your wish). They are not sorted in any order.
Optional - number of pairs


Output


An ASCII drawing that shows the actual links between the nodes. Nodes are given by a to z or A to Z. Use - for horizontal links and | for vertical links. Links may be of any (non-zero) length but they should be straight horizontal/vertical lines that do not bend. Spaces can be added provided they don't disfigure the picture.


You may not use built-ins that help in layout of the graph. Other graph-related built-ins may be allowed (though solutions without built-ins would be more appreciated). Shortest code wins.


Sample data

Input

A B
B F
B L
F K
L K
K R
K S
R P
S J
S P
J A
T V
V N


Output

A - B - F   T - V
|   |   |       |
|   L - K - R   N
|       |   |
J ----- S - P


Input

H C
G H
A B
B F
B C
F G
C D
D A


Output

A - B ----- F
|   |       |
D - C - H - G
CJam, 142
You didn't ask for an optimal, deterministic or fast solution, so here you go:
qN%Sf%::c_s_&amp;:Aff#:E;{A{;[DmrDmr]2f*}%:C;E{Cf=~.-:*}%0m1{E{Cf=$~1$.-_:g:T\:+,1&gt;\ff*\f.+T0=&quot;-|&quot;=f+~}%CA.++:L2f&lt;__&amp;=!}?}gS25*a25*L{~2$4$=\tt}/N*

Try it online
This generates random coordinates for each letter and tests if the layout is acceptable (edge letters lining up and no intersections), until it is. It gets mind-numbingly slow as you add more edges.
The two D letters in the code specify the maximum x and y coordinates; I picked D (=13) because I think it should be sufficient for all cases, feel free to prove me wrong. But you can change them to other values to speed up the program, e.g. the 2nd example should finish within a minute or two if you use 3 and 4 instead.