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:
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:
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
