Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Este problema consiste en implementar una estructura de conjuntos disjuntos persistente. ¿Qué significa esto?

Acerca de conjuntos disjuntos:

Se comienza con N elementos, cada uno de los cuales representa un conjunto de 1 elemento. Debemos ser capaces de responder dos tipos de pedidos:

+ a b – Mezcla el conjunto que contiene al elemento a con el conjunto que contiene al elemento b en un solo conjunto.

?  a b – Pregunta si a y b se encuentran en el mismo conjunto.

Acerca de la persistencia:

Ahora tenemos varias copias (versiones) de la estructura de conjuntos disjuntos.

Los pedidos entonces van a ser de la forma:

+ i a b – Se crea una nueva versión de la estructura de datos con la misma información que la i-ésima copia de la estructura, solamente que en esta nueva versión se mezclan los conjuntos que contienen al elemento a y al elemento b en un solo conjunto. Cabe destacar que en esta operación la i-ésima estructura no cambia. Más adelante se explica como se le asigna el número de versión a esta nueva copia.

? i a b – Pregunta si en la i-ésima versión de la estructura a y b se encuentran en el mismo conjunto.

Input

La primera línea de la entrada contiene dos números N (1 <= N <= 100 000) y K (0 <= K <= 100 000) que representan el número de elementos y el número de preguntas respectivamente. Inicialmente, todos los elementos se encuentran en conjuntos diferentes. L a versión inicial de la estructura es 0.

A continuación hay K líneas, cada una de las cuales contiene un pedido con el formato descrito anteriormente. Los pedidos se enumeran de 1 a K.

Si el j-ésimo pedido es de la forma + i a b, entonces la nueva versión que se crea va a tener el número j.

Output

Por cada pregunta de la forma ? i a b, debemos responder en una línea el resultado de esta pregunta, “Si”, indicando si en la i-ésima versión de la estructura a y b se encuentran en el mismo conjunto y “No” en caso contrario.

Sample test(s)