Problem #3562 - ECNU Online Judge

单点时限: 3.0 sec

内存限制: 1024 MB

在面向对象程序设计中，常常会运用到函数的扩展与重写。当一个类继承某个类的时候，它可以调用所有父类可以调用的函数。它可以声明新的函数。当新的函数签名与父类的某个函数一致时，就会发生函数的覆盖（重写）。所以，在子类的实例调用某个函数时，它会调用最近的父类（有可能是它自己）的那个函数实现。

这里我们不考虑访问权限等情况，我们只关心某个类在调用某个函数时，这个函数是在哪个类中实现的。

输入格式

输入具有如下格式：

$n p_{2} p_{3} \dots p_{n} t_{1} a_{11} a_{12} \dots a_{1 t_{1}} t_{2} a_{21} a_{22} \dots a_{2 t_{2}} ⋮ t_{n} a_{n 1} a_{n 2} \dots a_{n t_{n}} q u_{1} r_{1} u_{2} r_{2} ⋮ u_{q} r_{q}$

解释与数据规模约定：

$n$ 表示有 $n$ 个类，这些类从 $1$ 到 $n$ 编号。 $2 \leq n \leq 10^{5}$ 。
$p_{i}$ 表示第 $i$ 个类的父类编号。 $1 \leq p_{i} \leq i - 1$ 。第 $1$ 个类是所有类共同的祖先类，这个类没有父类。
$t_{i}$ 表示在第 $i$ 个类中定义了多少个函数， $a_{i 1}, a_{i 2}, \dots, a_{i t_{i}}$ 表示第 $i$ 个类中的函数列表。同一个类的函数列表中不会出现两个相同的函数。 $1 \leq a_{i j} \leq 10^{6}$ 。 $0 \leq t_{i} \leq 10^{6}, \sum t_{i} \leq 10^{6}$ 。
$q$ 表示询问个数。 $1 \leq q \leq 10^{5}$ 。
$u_{i}, r_{i}$ 表示第 $i$ 个询问，询问第 $u_{i}$ 个类的实例在调用 $r_{i}$ 函数时，调用的是哪个类中的版本。 $1 \leq u_{i} \leq n, 1 \leq r_{i} \leq 10^{6}$ 。

输出格式

对于每个询问，输出答案。如果调用不合法（会导致编译错误），输出 $- 1$ 。

样例

Input

Output

-1
3
4
-1

提示

样例等价于下面的 Java 代码。

class Class1 {
    void function2() { System.out.println("1"); }
    void function1() { System.out.println("1"); }
}

class Class2 extends Class1 {

}

class Class3 extends Class2 {
    void function5() { System.out.println("3"); }
    void function2() { System.out.println("3"); }
}

class Class4 extends Class3 {
    void function4() { System.out.println("4"); }
    void function5() { System.out.println("4"); }
}

class Class5 extends Class3 {
    void function5() { System.out.println("5"); }
}

void test() {
    new Class3().function4();
    new Class5().function2();
    new Class4().function5();
    new Class1().function3();
}

91 人解决，242 人已尝试。

119 份提交通过，共有 1414 份提交。

5.5 EMB 奖励。

创建: 6 年，11 月前.

修改: 6 年，11 月前.

最后提交: 1 月前.

来源: 2018 华东师范大学校赛

data structure

3562. 面向对象程序设计

输入格式

输出格式

样例

提示

服务

开源

关于我们