És un AVL? P34834

Considereu un arbre representat amb un graf dirigit amb $n$ vèrtexs i $n-1$ arcs, on cada arc $x \to y$ indica que el node amb clau $x$ és pare del node amb clau $y$. Digueu si l’arbre representat pot ser un arbre binari de cerca AVL o no. Podeu triar l’ordre més convenient per als fills de cada clau.

Entrada

L’entrada consisteix en diversos casos, cadascun amb $n$, seguida d’$n$ claus diferents, seguides de $n-1$ parells $x$ $y$, indicant que $x$ és pare de $y$. Suposeu $1 \le n \le 10^4$, que les claus són enters entre $-10^9$ i $10^9$, i que el graf representa un arbre.

Sortida

Per a cada graf, escriviu “yes” si representa un arbre binari de cerca AVL, i “no” altrament.