Problem C
Amigolândia

A Amigolândia é uma cidade na qual amizades são levadas muito seriamente. Todos seus habitantes tem um e apenas um melhor amigo, de forma que se o melhor amigo de $i$ é $j$, o melhor amigo de $j$ é $i$.

Cada habitante de Amigolândia mora em uma casa, essas casa são conectadas por ruas bidirecionais de forma que há exatamente um caminho simples entre qualquer par de casas.

João tem alguns amigos em Amigolândia que ele quer visitar, mas ele ainda não decidiu que rota irá tomar. Ele sabe que vai escolher amigos $a$ e $b$, e partindo da casa de $a$ vai visitar todas as pessoas com casas localizadas no caminho mínimo até a casa de $b$.

Infelizmente, amigolandianos são muito orgulhosos. Se, para algum par de melhor amigos $(i,j)$, João visitar $i$ e não visitar $j$, $j$ irá odiar João para sempre.

Como Amigolândia quer manter sua comunidade amigável, se alguém passar a ser odiado, essa pessoa está banida da Amigolândia para todo o sempre.

Ajude João a não ser banido da Amigolândia.

Entrada

A primeira linha da entrada contém dois inteiros $N$ e $Q$, ($1 \leq N, Q \leq 10^5$, $N$ é par), o número de habitantes de Amigolândia e o número de trajetórias que João está considerando, respectivamente.

As $N-1$ linhas seguintes são pares $i$ $j$ indicando que existe uma rua entre $i$ e $j$.

As $N/2$ linhas seguintes são pares $i$ $j$ indicando que $i$ e $j$ são melhores amigos. É garantido que cada habitante aparece apenas uma vez nos pares de melhores amigos.

As $Q$ linhas seguintes são pares $a$ $b$, indicando que João está considerando ir da casa do habitante $a$ à casa de $b$.

Saída

Para cada trajetória considerada por João, imprima “:)” se ele consegue realizar a trajetória sem ser banido da Amigolândia e “:(” caso contrário.

6 5
1 2
2 3
3 4
4 5
5 6
1 2
3 5
4 6
1 2
2 6
4 6
3 6
3 5

:)
:(
:(
:)
:(