ZOJ Problem Set - 2567
In the Middle Ages m European cities imported many goods from n Arabian cities. Due to continous feudal wars, European cities did not trade with each other, so is some European city needed some Arabian goods, the special trade route was established for this particular trade.
Studying the manuscripts historians have found out that each European city imported goods from at least two Arabian cities, and each Arabian city exported goods to at least two European cities. They have also investigated different factors and identified all potential trade routes (trade routes between some pairs of cities were impossible due to various reasons).
Now historians wonder, what is the minimal possible number of trade routes, that could have existed. Help them to find that out.
The first line of the input file contains m, n, and p - the number of European and Arabian cities respectively, and the number of potential trade routes (1 <= m, n <= 300, 1 <= p <= nm). The following p lines describe potential trade routes, each description consists of two numbers - the European and the Arabian city connected by the route.
On the first line of the output file print k - the minimal possible number of trade routes that could have existed. After that output k numbers - some minimal set of routes that might have existed to satisfy all conditions. Routes are numbered starting from 1 as they are given in the input file.
If historians must have made a mistake and it is impossible to satisfy the specified conditions, print -1 on the first and the only line of the output file.
5 5 14 1 2 1 3 1 4 1 5 2 1 2 5 3 1 3 5 4 1 4 5 5 1 5 2 5 3 5 4
12 1 2 3 5 6 7 8 9 10 12 13 14
Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #4