You are visiting a colorful tree in the dream of Electric Sheep, which has at most
606060 colors. These colors are numbered from
000 to
595959.
The colorful tree has
nnn vertices, connected with
n−1n - 1n−1 edges. Each vertex is painted in some of the colors. Let non-negative integer
cic_ici denotes the colors of vertex
iii. If the lowest
jjj-th bit of
cic_ici is
111, the colors that vertex
iii is painted contains color
jjj. Note that a vertex can be painted in no colors, which means this vertex is transparent.
You also have your own color
ccc. When you are travelling on the colorful tree, you can visit vertex
iii iff the colors of vertex
iii contains your color
ccc. If you are at vertex
uuu and your color is
ccc, you can do one of the following operations in
111 second:
-
Move to vertex vvv that is adjacent to vertex uuu.
Note that both the colors of vertex uuu and those of vertex vvv should contain color ccc.
-
Choose a color c′c'c′ and change your color to c′c'c′.
Note that the colors of vertex uuu should contain both color ccc and c′c'c′.
Now you are planning for
qqq trips. The
iii-th trip is planned from vertex
uiu_iui to another vertex
viv_ivi. You can choose any color you want as your color
ccc at vertex
uiu_iui before the trip. Find out the number of seconds that need to be taken to arrive at vertex
viv_ivi in the optimal way for each trip.
If you can’t reach vertex
viv_ivi from vertex
uiu_iui, print
−1-1−1.