Problem C
Friendland

Friendland is a city where friendship is taken very seriously. Every citizen has one and only one best friend. If $j$ is $i$’s best friend, then $i$ is $j$’s best friend too.

Each citizen from Friendland lives in a house. These houses are connected by bidirectional roads and there is only one simple path between any pair of houses.

João wants to visit some friends in Friendland, but he doesn’t know which path to take yet. He knows he will choose friends $a$ and $b$, and, starting from $a$’s house, will visit all citizens with houses in the path to $b$’s house.

Unfortunately, Friendlandians are very proud. If João visits $i$ but doesn’t visit his best friend $j$, $j$ will hate João.

Friendland wants to keep the community friendly. If anyone is hated by any citizen, that person will be banned from Friendland for all eternity.

Help João not get banned from Friendland.

Input

The first line of input contains two integers, $N$ and $Q$, ($1 \leq N, Q \leq 10^5$, $N$ is even), the number of citizens and the number of paths João is considering taking, respectively.

The following $N-1$ lines are pairs of integers $i$ $j$, meaning there is a road from $i$’s house to $j$’s house.

The following $N/2$ lines are pairs of integers $i$ $j$, meaning that $i$ and $j$ are best friends. It is guaranteed that every citizen appears only once on the pairs of best friends.

The following $Q$ lines are pairs $a$ $b$, meaning that João is considering taking the path from $a$’s house to $b$’s house.

Output

For each path João is considering, print “:)” if he will not be banned by taking it, and “:(” otherwise.

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

:)
:(
:(
:)
:(