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 eq.not 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 <= n <= 10^5$, $1 <= b <= 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 <= k_i <= b$) which describes the number of topics student $X_i$ knows. Next $k_i$ integers will be the topics $t_k$($1 <= t_k <= b$) that student $X_i$ knows perfectly.
Next line will contain integer $q$ ($1 <= q <= 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 $t y p e_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$.
## Input
The first line contains two integers $n$ and $b$ ($1 <= n <= 10^5$, $1 <= b <= 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 <= k_i <= b$) which describes the number of topics student $X_i$ knows. Next $k_i$ integers will be the topics $t_k$($1 <= t_k <= b$) that student $X_i$ knows perfectly.Next line will contain integer $q$ ($1 <= q <= 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 $t y p e_i in {0, 1, 2}$, then the rest of the input for that event goes as follows: if $t y p e_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 $t y p e_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 $t y p e_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 <= k_i <= b$) which describes the number of topics student $X_i$ knows. Next $k_i$ integers will be the topics $t_k$ ($1 <= t_k <= 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.
## Output
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$.
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of students currently in class, $ b \in \mathbb{Z}^+ $ the number of topics ($ 1 \leq b \leq 20 $).
Let $ S $ be the set of students currently in class.
For each student $ x \in S $:
- Let $ f(x) \in S \cup \{x\} $ denote $ x $'s favorite partner.
- Let $ T(x) \subseteq \{1, 2, \dots, b\} $ denote the set of topics student $ x $ knows perfectly.
Define the *special partner relation* $ \sim $ as the transitive closure of the relation $ x \to f(x) $, with $ x \sim x $, and $ \sim $ is anti-symmetric: if $ x \sim y $ and $ x \ne y $, then $ y \not\sim x $.
This induces a partition of $ S $ into disjoint *groups* (strongly connected components under $ \sim $), where each group is a set of students mutually reachable via the favorite relation, with no mutual reachability between distinct groups.
For any group $ G \subseteq S $, define its *knowledge set* as $ T(G) = \bigcup_{x \in G} T(x) $.
The *grade* of group $ G $ is $ |T(G)| $.
**Constraints**
1. $ 1 \leq n \leq 10^5 $, $ 1 \leq b \leq 20 $
2. Each student ID is unique and $ \leq 10^9 $
3. For each student, $ 1 \leq |T(x)| \leq b $, topics are integers in $ [1, b] $
4. $ 1 \leq q \leq 10^5 $ events
**Events**
- Type 0: Add a new student $ x $ to class with favorite $ f(x) $ and topic set $ T(x) $.
- Type 1: Query — given two students $ x, y \in S $, find the minimum grade of the smallest group containing both $ x $ and $ y $. If no such group exists (i.e., $ x $ and $ y $ are in different components), output $ -1 $.
- Type 2: Remove a student $ x $ from class.
**Objective**
For each type-1 event, compute:
$$
\min_{\substack{G \subseteq S \\ x,y \in G}} |T(G)| \quad \text{where } G \text{ is the unique group containing } x \text{ and } y
$$
If $ x $ and $ y $ are not in the same group, output $ -1 $.