MOG Round #14Ended |
Este problema consiste en implementar una estructura de datos similar a un Conjunto Disjunto. Esta es una colección de conjuntos disjuntos que soportan tres operaciones :
$\texttt{1 p q}$ | Une los conjuntos en donde se encuentran $p$ y $q$. De $p$ y $q$ estar en el mismo conjunto se ignora esta operación. |
$\texttt{2 p q}$ | Mueve el elemento $p$ al conjunto donde se encuentra el elemento $q$. De $p$ y $q$ estar en el mismo conjunto se ignora esta operación. |
$\texttt{3 p}$ | Retorna la cantidad de elementos que se encuentra en el conjunto donde se encuentra $p$ y la suma de sus elementos. |
Inicialmente la colección contiene $n$ conjuntos: $\{\{1\}, \{2\}, \{3\}, \{4\}, ..., \{n\}\}$
Cada entrada contiene multiples casos de prueba. Por cada caso de prueba la primera línea son dos enteros separados por un espacio, $n$ y $m$ $(1 \leq n,m \leq 100000)$ que representan la cantidad de enteros y la cantidad de comandos. Luego las m líneas siguientes contienen un comando, cada uno de estos comandos garantiza $1 \leq p, q \leq n$. La entrada termina cuando se termina el fichero $\texttt{EOF}$. Los ficheros de entrada no exeden los 5mb.
Para cada comando del tipo $3$, imprime dos enteros, la cantidad de elementos y la suma de ellos.