← 返回题目列表

Codeforces · 739/D

D. 恢复功能图

中文机器翻译题面 查看原题

函数图是一个有向图,其中所有顶点的出度都等于 1。允许循环。

函数图的某些顶点位于环上。从其他问题中,我们可以通过沿着边缘进行有限数量的步骤来形成一个循环(在这个问题中我们只考虑有限的函数图)。

让我们计算每个顶点的两个值。 precyclei 是我们应该通过的边数来到达某个循环的一部分的顶点(零,如果 i 本身位于一个循环上),cyclei 是我们到达的循环的长度。

您将获得有关某些函数图的这些值的信息。对于每个顶点,您都知道值 precyclei 和 Cyclei,但是,可能会出现问号,而不是某些值。这意味着这些值是未知的。

构建任何适合描述的函数图或确定不存在这样的图。

输入

第一行包含单个整数 n (1 ≤ n ≤ 300) — 图中的顶点数。

接下来的 n 行中的每一行都包含两个整数 — precyclei (0 ≤ precyclei ≤ n - 1) 和 Cyclei (1 ≤ Cyclei ≤ n)。可能会有问号而不是其中一些值。

输出

如果没有解决方案,则打印-1。

否则,打印 n 个整数。其中第 i 个是第 i 个顶点的边所到达的顶点数。

顶点的顺序应与输入数据中的顺序相同。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3
0 3
0 3
? ?

输出 #1

2 3 1

输入 #2

5
3 2
? ?
? ?
? ?
? ?

输出 #2

5 3 2 2 4

输入 #3

8
? 3
? ?
0 2
0 2
0 3
0 3
0 3
3 3

输出 #3

5 1 4 3 6 7 5 2

输入#4

1
? ?

输出#4

1

输入 #5

6
0 3
0 3
0 3
0 3
0 3
0 3

输出 #5

2 3 1 5 6 4

输入 #6

2
1 1
1 1

输出 #6

-1