ROMANRDS - Roman Roads

no tags 

Some 2000 years ago the Roman Empire covered a large part of Europe including the entire coast of the Mediterranean. The transportation network of that empire consisted of roads and sea routes (the two are considered equivalent and simply called roads for this problem). Each road connected exactly two cities and the road network was such that every city can be reached from Rome. However, building this network required resources (cobblestone and buoys) proportional to the total length of the network. In order to cut down on building costs and maintainance and spend the rest of the money on wine, the empire built the cheapest possible network.

Additionally, each road had a single signpost that listed all of the other roads it connected to (at any of its two cities). There were N roads in the empire labeled 1, 2, ..., N. It is believed that a traveller once travelled all roads and for each road wrote down the numbers on its signpost, thus making a map.

2000 years later a young archaeologist found something that looks suspiciously like that map. Your job is to write a program that determines if this can really be a map of the Roman empire and for each road output the two cities it connected. Note that roads in a valid map are always between two distinct cities.

(Disclaimer: The description of the transportation network is for this problem only and may not necessarily be what the Roman Empire actually did. Do not cite this in your history papers: I made it up.)


The first line of input contains N, 1N500. Each of the next N lines contains a space-separated list of integers. The i-th of these lines describes the "roads" that connect to "road" i. The first number on the line specifies the number of those "roads", di, and the following di numbers specify their labels.

Note that although at this point we don't know if the map is valid, the input is consistent, i.e. if a road x is on the signpost of y, then y will be on the signpost of x. (Otherwise the archaeologist would know this is not a Roman map right away).


If the input cannot describe a valid map according to the description, output "NO" on the first (and only) line of output.

Otherwise, output "YES" and on each of the next N lines, write two integers separated by space, the numbers of the two cities that the road connected. City labeling is up to you with the only restriction that all city labels must be integers between 1 and M, where M is the total number of cities. Of course, a city can only have one label.

Note that since we don't know the actual locations of the cities or whether the roads were straight, we have no idea what the total cost of the network might have been. The archaeologist is willing to accept any map for which she can't determine if there is a cheaper network without knowing the actual costs. It is assumed that each road had some positive cost.


2 3 2
2 1 3
2 2 1

1 3
4 1
1 2

hide comments
Buda IM (retired): 2015-03-25 19:37:53

Note that you cannot output just any graph, but first line should specify first edge described in the input!

Last edit: 2015-03-25 20:28:26
:D: 2010-07-10 14:16:18

"if a road x is on the signpost of y, then y will be on the signpost of x" I think you can also assume that on every signpost every road is printed at most once.

Added by:Minilek
Time limit:8.614s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:MIT Individual Contest 2007