405219: GYM101848 C Object-Oriented Programming

Functions overriding, is a well-known concept, when we are using inheritance in Object-Oriented Programming (OOP). For those who are not familiar with OOP, I will recall a few things to perhaps refresh your memory.

• A class has at most one parent class. When they do, they are called subclasses inheriting their parents. Subclasses also inherit all the functions declared in their parent classes, and also, all the functions inherited by parents' parents, and so on. Here, we refer to the ancestors as superclasses.
• Subclasses can, of course, declare new functions, and also override the functions already declared in superclasses. This is called overriding.
• When an instance of the subclass calls a function, it will first try to find the code in its own class body, and then its parent, and then its parent's parent, etc., until it reaches the root (the superclass of all classes). If the function has still not been found yet, a runtime error will be raised.

As you might have guessed, we are interested in finding out in which class the function is written when some instance of a particular class calls it.

The input is in the following format:

n (2 ≤ n ≤ 10⁵) is the number of classes. Classes are numbered from 1 to n. p_i (1 ≤ p_i ≤ i - 1) is the parent class of class i. Class 1 is the root class, superclass of all classes. It has no parent.

t_i denotes the number of functions written in class i, including both new functions and overriding functions. Then follows a_i1, a_i2, ..., a_iti a list of these functions. Functions are also denoted using positive integers. It's guaranteed that every number will appear at most once in one list. 1 ≤ a_ij ≤ 10⁶, 0 ≤ t_i ≤ 10⁶, .

q (1 ≤ q ≤ 10⁵) is the query number. Then follows q queries. u_i, r_i (1 ≤ u_i ≤ n, 1 ≤ r_i ≤ 10⁶) is the i-th query, asking when an instance of class u_i calls function r_i, in which class is this function written?

For each query, print answer. If it is illegal, that is, a "runtime error" is raised, then output  - 1.

5
1 2 3 3
2 2 1
0
2 5 2
2 4 5
1 5
4
3 4
5 2
4 5
1 3

-1
3
4
-1

The sample is equivalent to the following Java code.

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();
}

Some of the tests in the raw problem package have been removed due to the "Maximal summary testset file size exceeded" error on Codeforces.