The option finds a reasonable tour through a graph that visits every node. The distance between two nodes must always be less than the distance between them via a third node.

The order of visiting nodes will be displayed, with a graphical representation.

Input

Input is accepted in two formats, cities or links, of space delimited text files

Format

The first line specifies the calculation required. It must contain

format sales

Cities

Column	Description
1	'c' for city
2	x location
3	y location
4	name

The cities will all be connected by links with cost equivalent to the Pythagorean distance between them.

Links

Column	Description
1	l for link
2	src node name
3	dst node name
4	cost

Links will be added between nodes where missing with cost set to a large number. This allows a tour to be found if a critical link is missing, but otherwise only links present in the input will be used.

Example