Conectividad directa de un Árbol Binario

Time Limit:
5 Sec
Memory Limit:
128Mb
Enviados:
213
Resuelto:
82

Descripción

Un árbol binario es una estructura de datos jerárquica utilizada en informática, está compuesto por nodos enlazados de una manera particular. Cada nodo en un árbol binario tiene como máximo dos hijos, que se denominan comúnmente hijo izquierdo e hijo derecho.


Algunas definiciones útiles son:

  • Nodo: Cada elemento en un árbol binario se llama nodo. Cada nodo puede tener un valor o dato asociado, y puede tener como máximo dos hijos.
  • Raíz: El nodo en la parte superior del árbol se llama raíz. Es el nodo principal desde el cual se originan todos los demás nodos.
  • Hijo Izquierdo e Hijo Derecho: Cada nodo puede tener hasta dos hijos: uno que se considera el hijo izquierdo y otro que se considera el hijo derecho.
  • Hoja: Un nodo que no tiene hijos se llama hoja o nodo terminal. Son los nodos en la parte inferior del árbol.
  • Nodo Padre: Un nodo padre es un nodo que tiene uno o más hijos. Cada nodo en el árbol, excepto la raíz, tiene un padre.

Se te dará un árbol binario infinito (casí infinito) del cual el nodo raíz empezará con el valor 1 y que cada nodo tendrá siempre tendrá 2 hijos . Por lo tanto, el árbol binario infinito (casí infinito) será de la siguiente manera:

(Los primeros 4 niveles del árbol binario infinito)

Se te pide que revises si el nodo a tiene una conexión directa con el nodo b.

Entrada

La entrada consiste en un número entero $t$  $(1 \leq t \leq10^5)$ – La cantidad de casos de prueba.
Para cada caso: Se te darán $2$ números enteros $a$ y $b$ $(1 \leq a < b \leq10^{18})$ – Los $2$ nodos de los cuales quieres ver si tienen conexión.

Salida

Para cada caso imprimir “SIUUU :D” si es que el nodo a tiene una conexión directa con el nodo b, caso contrario imprimir “NOUUU :c”.

Ejemplo Entrada

Copy icon
6
15 30
60 61
67 100
1000 2000
1 5
1 3

Ejemplo Salida

Copy icon
SIUUU :D
NOUUU D:
NOUUU D:
SIUUU :D
NOUUU D:
SIUUU :D

Ayuda