Statement
skeep 팬클럽의 멤버로 활동 중인 호반우는 임원진이 되고 싶어 클럽장인 skeep한테 부탁하여 다음과 같은 임무를 받게 되었다.
현재 호반우는 유명인사 skeep의 이름을 딴 대륙인 skeep land에 와 있다.
skeep land에는 개의 지점이 존재하며, 지점들은 도로로 연결되어 하나의 트리를 이룬다.
각 지점에는 팬클럽이 하나씩 위치해 있으며, 해당 팬클럽의 소속을 나타내는 정수 가 할당되어 있다. 인 경우 해당 지점에는 skeep 팬클럽이 위치해 있음을 의미한다.
AND 연산이 뭔가요?
는 비트 단위 AND 연산을 의미한다. 두 정수를 2진수로 나타냈을 때 같은 위치의 비트가 모두 1인 경우에만 결과의 해당 비트가 1이 되고, 그렇지 않으면 0이 된다.
예를 들어, , 이므로 이다.
Input
첫 번째 줄에는 팬클럽 지점의 개수와 쿼리의 개수 , 가 공백으로 구분되어 주어진다. (), ()
Output
각 쿼리마다 조건을 만족하는 두 팬클럽 지점을 선택했을 때의 거리를 출력한다.
만약 조건을 만족하는 두 지점이 존재하지 않는다면, -1을 출력한다.
Samples
Sample 1
Input
5 2
1 2 3 4 5
1 2 3
2 3 7
2 5 3
5 4 1
7
0
Output
11
-1
Sample 2
Input
5 3
0 0 0 1 2
1 2 3
2 3 7
2 5 3
5 4 1
1
2
3
Output
1
1
1
Sample 3
Input
5 1
1 1 1 0 0
1 2 3
2 3 7
2 5 3
5 4 1
999
Output
-1