函数图是一个有向图,其中所有顶点的出度都等于 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