Problem name: Find the map
Problem ID: 19007
Problem setter: Stefan Ciobaca
Problem input: standard input
Problem output: standard output
The map of the lost city has been lost. There is only little information
left. It is a known fact that the map contained N important points. Any two
of them could have been connected using a one way link (e.g. if point A was
connected to point B, point B wasn't necesarely connected to point A). Also
there may be at most one connection from point A to point B.
You have found some more information about the map. You know for each of
the N important points exactly how many points were connected to it and how
many points it was connected to. You are thinking about making lots of money
by selling a reconstruction the map.
So you should write a program, that, given the above information, will
construct a version of the map (there may be more solutions, your program
will only need to find one).
The first line contains number N, the number of important points. The
points are numbered from 1 up to N.
On line I + 1, I = 1,N, you will find two space separated values: the
first number DI[i] is the number of important points which are connected to
point I and the second one DE[I] is the number of important points to which
point I is connected.
If there is no solution (the information you got must have been fake) you
will only write one line with a -1. Otherwise, you should write:
On the first line, the number of connections M.
On the next M lines, you will write two number A and B, meaning that
point A is connected to point B.
- 1 <= N <= 100
- There can't be a link between a point to itself
- 0 <= DI[i], DE[i] <= 100, for i=1,N
- Time limit: 1 second
- Output limit: 1 MB
- Data limit: 1 MB
- Stack limit: 1 MB