Island of straight roads

Time limit = 5 seconds

Recently robots found that their economics is rather good and they may start traveling over the island, seeing different places and robots. In fact they just start feeling taste of life.

Robot-inventors discover very efficient and cheap transport, but for one restriction all roads should be straight lines connecting two towns.

Robot's economics is not so good to build road between every two towns. Besides there are ditches that roads can't cross.

They want to build system of roads that allows traveling from any town to any another town and besides has minimum possible total length.

Help them. They can't solve the problem without your help, because they start feeling and forget all the classic algorithms. (If fact they do not want to waste their energy on algorithms)

Think of towns as points. Think of roads and ditches as segments. Ends of any road should be towns.

Input The first line contains number of towns N and number of ditches M. N, M ≤ 200.

Then N lines follow with town description. Each line contains town name (word of length 20 characters of less) and two coordinates of the town:

Then M lines follow. Each line contains four numbers — coordinates of the first and second end of the ditch:

All coordinates are integers and their absolute values are less than 100 000.

Output If there is possibility to build roads connecting all towns together, then output line with 'YES'. The second line should contain number of roads R and next R lines should describes roads: each line should contain two town names.

If ditches do not allow building roads, then output one line with 'NO'.

2 1
Moscow 0 0
Kiev 2 0
1 -1 1 1

NO

3 1
Moscow 0 0
Kiev 2 0
Volgograd 1 2
1 -1 1 1

YES
2
Moscow Volgograd
Volgograd Kiev

Author:
Voroztsov Artem
18 February 2003

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