Recover a functional graph
Contest: Codeforces Round 381 (Div. 1)
Difficulty rating: 3400
Tags: graph matchings

Functional graph is a directed graph in which all vertices have outdegree equal to 1. Loops are allowed.

Some vertices of a functional graph lay on a cycle. From the others we can come to a cycle by making a finite number of steps along the edges (we consider only finite functional graphs in this problem).

Let's compute two values for each vertex. precyclei is the amount of edges we should pass to get to a vertex which is a part of some cycle (zero, if i itself lies on a cycle), cyclei is the length of the cycle we get to.

You are given the information about these values for some functional graph. For each vertex you know the values precyclei and cyclei, however, instead of some values there can be the question mark. It means that these values are unknown.

Build any functional graph that suits the description or determine that there is no such graph.

Input format:
The first line contains single integer n (1 ≤ n ≤ 300) — the number of vertices in the graph.

Each of the next n lines contain two integers — precyclei (0 ≤ precyclei ≤ n - 1) and cyclei (1 ≤ cyclei ≤ n). There could be question marks instead of some of these values.

Output format:
In case there is no solution, print -1.

Otherwise, print n integers. i-th of them is the number of vertex to which the edge form the i-th vertex go.

The vertices should be in the same order as they go in input data.

If there are multiple solutions, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3
0 3
0 3
? ?

Example output:
2 3 1

Example input:
5
3 2
? ?
? ?
? ?
? ?

Example output:
5 3 2 2 4

Editorial:
Let's think what has to hold after we put numbers in place of question marks:
1. number of vertices with precycle = 0 and cycle = y should be divisible by y.
2. if there exists a vertex with precycle = x > 0 and cycle = y, then there should also exist a vertex with precycle = x - 1 and cycle = y.
Now looking at vertices without question marks, let's count for every cycle length y how many vertices have to be added for condition 1 to hold (keeping in mind that this number cannot be 0 if there exist vertices of the form (x, y) or (?, y)) and which precycle lengths are missing for condition 2 to hold.
Here it's important that for 2 we have to consider vertices of the form (x, ?). Specifically, in order for everything to be univocally determined, it is necerrary to try all the cycle lengths for the vertex of this form with maximal x. Some contestants tried to assign cycle lengths for such vertices greedily and got WA#15.
Let's build the network for the flow which will have two parts. Vertices of the left part will correspond to the vertices of the functional graph that have at least one question mark. Vertices of the right part are the requirements of the form "need k vertices of the form (0, y)" (for 1 to hold) and "need one vertex of the from (x, y)" (for 2 to hold). Add edges from the source to the left part, form the right part to the sink, and between requirements and vertices that satisfy them. If done correctly, with only one vertex created in the left part for all vertices of the same form in the functional graph, there will be O(n) nodes and O(n) edges in the network and the maximum flow will also be O(n). Edmonds-Karp algorithm, which works in O(E * flow) will work in O(n2) on this network. Accounting for the bruteforce of the cycle length for the maximal vertex of the form (x, ?) we get O(n3) for the whole solution. In practice, any decent algorithm for finding maximum flow would most likely pass the system testing. Dinic works in 15 ms.
If all of the vertices in the right part are saturated - the answer is found. Rolling back the flow, we will find which vertices in the left part saturated which ones in the right part. Now we can change the question marks to numbers for those vertices in the left part, that were used, but some question marks might still remain. This is no big deal. Let's change all vertices of the form (x, ?) to (x, maxc), where maxc is that cycle length we bruteforce in the outermost loop. Instead of vertices of the form (?, y) we can write (1, y). Remember, that we created at least one cycle for all such y's. Instead of (?, ?) simply put (0, 1).
Now it's quite simple to get the answer to the problem. First create cycles out of the vertices of the form (0, y), and then add edges (x, y) -> (x - 1, y).