Matcom Online Grader

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)