P9867 [POI 2021/2022 R2] kon

Translated from [POI2021~2022R2 Day2T2](https://szkopul.edu.pl/problemset/problem/TEuljz3gsotYQRUKdlEZZr1G/statement/)。

There is a dance party. At the beginning, there are only persons $1$ and $2$, and both of them are willing to dance with each other. Then there are $q$ events, corresponding to the following operations: - `W x`: A new person joins. They and person $x$ are mutually willing to dance with each other. - `Z x`: A new person joins. Initially, they are mutually willing to dance with everyone that person $x$ is willing to dance with. - `? x`: Query how many people are willing to dance with $x$. The new person’s index is the current number of people plus one.

The first line contains an integer $q\ (1 \leq q \leq 10^6)$. Then follow $q$ lines. Each line contains a character and an integer $x$, with the meaning as described above.

For each `?` operation, output one line with the answer.

Sample explanation:  Subtasks: | Subtask ID | Special property | Score | | :----------: | :----------: | :----------: | | $1$ | $q \leq 5000$ | $20$ | | $2$ | Only operations `Z` and `?` | $10$ | | $3$ | `?` always appears in the final part of the $q$ operations | $35$ | | $4$ | No additional constraints | $35$ | Translated by ChatGPT 5