407240: GYM102700 J Java exam

It's the end of the semester and students are really tired after having virtual classes. Next Monday guys of programming class have their final exam in Java. To avoid cheating, the teacher decided to allow them to take the exam in groups.

It is always difficult to form the groups because everybody has different preferences when choosing partners to work with. In particular, each student has a favorite partner. Of course, it is possible that a student doesn't like to work with anyone else, in this case, his favorite partner is himself.

Moreover, students have special partners, a student $$$Z$$$ is a special partner of student $$$X$$$ if $$$Z = X$$$ or if $$$Z$$$ is a special partner of the favorite partner of $$$X$$$. Also this relation is anti-symmetric, i.e. if $$$Z \neq Y$$$ and $$$Z$$$ is a special partner of $$$X$$$ then $$$X$$$ cannot be a special partner of $$$Z$$$.

Considering this, for 2 students $$$X$$$ and $$$Y$$$ to be in the same group the following conditions have to be met:

• $$$X$$$ and $$$Y$$$ are part of the group.
• If student $$$Z$$$ is in the group then either the favorite partner of $$$Z$$$ is in the group or $$$Z$$$ is a special partner of all students in the group.
• There should be at least one student in the group who is a special partner of all students in the group.

The Java exam will consist of a limited number of exercises, each one related to a unique topic taught during the semester. For each exercise, the teacher will choose randomly one member of the team and this student will explain the solution of the corresponding exercise. Of course, a student is able to explain a solution correctly if and only if the student knows perfectly the corresponding topic. The number of exercises explained correctly will be the grade of the exam for the whole group.

The teacher distinguishes very well his students and the topics they know, so he decided to get some statistics about the exam during today's class. Given students $$$X$$$ and $$$Y$$$, he wants to know what would be the minimum grade that would get the smallest group containing those students. However, at the moment he decides to get a statistic, he only takes into account the students that are currently in class (yes, it's possible that some students arrive late or even go out early from class).

Since you got really bad scores on previous exams and you need extra credit, you decided to help your teacher to calculate the statistics during the whole class.

The first line contains two integers $$$n$$$ and $$$b$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le b \le 20$$$) — The number of students that are already in class and topics in the exam, respectively.

The following $$$n$$$ blocks of input will describe the information for each student that is already in class. The $$$i$$$-th block consists of $$$2$$$ lines described as follows:

The first line will contain two integers $$$X_i$$$ and $$$f_i$$$ meaning that student $$$X_i$$$ is currently in class and $$$f_i$$$ is his favorite partner. The second line starts with an integer ($$$1 \le k_i \le b$$$) which describes the number of topics student $$$X_i$$$ knows. Next $$$k_i$$$ integers will be the topics $$$t_k$$$($$$1 \le t_k \le b$$$) that student $$$X_i$$$ knows perfectly.

Next line will contain integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — The number of events that occurs during the class.

The following $$$q$$$ blocks of input will describe the information of each event happening during class. The $$$i$$$-th block starts with the type of event $$$type_i \in \{0, 1, 2\}$$$, then the rest of the input for that event goes as follows:

• if $$$type_i = 0$$$, it will be followed by one integer $$$X_i$$$ meaning that student $$$X_i$$$ left the class. It is guaranteed that this student is currently in class and once a student leaves, he never comes back.
• if $$$type_i = 1$$$, it will be followed by two integers $$$X_i$$$ and $$$Y_i$$$, meaning that you want to calculate statistics for students $$$X_i$$$ and $$$Y_i$$$.
• if $$$type_i = 2$$$, it will be followed by two integers $$$X_i$$$ and $$$f_i$$$ meaning that student $$$X_i$$$ has just arrived to class and student $$$f_i$$$ is his favorite partner. It is guaranteed that student $$$X_i$$$ wasn't before in class. In this case, there is another line of input, it starts with an integer ($$$1 \le k_i \le b$$$) which describes the number of topics student $$$X_i$$$ knows. Next $$$k_i$$$ integers will be the topics $$$t_k$$$ ($$$1 \le t_k \le b$$$) student $$$X_i$$$ knows perfectly.

Each student is identified uniquely by an integer which does not exceed $$$10^9$$$.

Note that it is possible for some students to never arrive to class.

For each event of type $$$1$$$ print the minimum grade that would get the smallest group with students $$$X_i$$$ and $$$Y_i$$$. If a group can't be formed with the students in class print $$$-1$$$.

1 1
1 2
1 1
1
1 1 1

1

7 4
1 2
1 4
2 3
1 1
3 4
4 1 2 3 4
4 5
4 3 1 2 4
5 6
4 1 4 2 3
6 7
3 1 2 4
7 7
4 4 1 2 3
8
1 3 5
1 5 7
0 4
1 3 5
2 8 4
4 3 4 1 2
1 8 4
1 8 8
1 1 1

4
3
-1
-1
4
1