Indian Computing Olympiad

Network Flows→Evil Intentions (IOITC 2005)

Tanmoy is searching for some special directed graphs so that he can force 90% of the submissions to time out. For each graph, his test data generator requires the vertices v1,v2,…,vN to have indegrees i1,i2,…,iN and outdegrees o1,o2,…,oN.

For instance, suppose the sequence of indegrees required is 0,1,2,2 and the sequence of outdegrees required is 2,1,1,1. Here is a graph with the required properties.

              v1------> v3
                 \   /  ^
                   X    |
                  / \   |
                <-   -> |
              v2 -----> v4
      

Your task is to help him construct a graph that meets his requirements or report that no such graph exists, so Tanmoy has to find another way to achieve his evil goal.

Solution

---