씨씨

성씨가 '씨'인 혈통은 전 세계에 총 N명이 있다. 2019년 5월 11일, '씨'씨 혈통의 모든 사람이 한자리에 모인 날이다.

하지만 누군가에게는 괴로운 날이다. 성씨가 씨이고 이름이 씨인 '씨씨'는 모임이 끝나면 '씨'씨 혈통의 족보를 완성해야 한다.

'씨'씨 혈통의 모든 사람은 시크릿하기 때문에 자신을 직접 소개하기를 무척 꺼린다. 족보를 완성해야 하는 '씨씨'는 총 M개의 대화를 엿들어 두 사람이 부르는 호칭을 듣고 그 촌수를 알아낼 수 있었다.

내일은 큰 어르신께서 족보를 인쇄하기 전에 검사하러 오실 예정인데, 어떤 사람 a와 b가 몇 촌인지 빠르게 맞춰야 검사를 통과할 수 있다. 편의상 사람은 번호로 나타내며, 오늘 모임에 참석한 순서대로 1번부터 N번까지 있다.

만약 검사를 하나라도 통과하지 못한다면 가문에서 쫓겨날 위기에 처해 있다. 아직 모든 연결 관계를 외우지 못한 '씨씨'는 이대로라면 위험하다. '씨씨'가 Q번의 검사를 모두 통과할 수 있도록 도와주자.

첫째 줄에 이 성씨의 인구 N과 엿들은 대화의 수 M이 주어진다. (2 ≤ N ≤ 200, 1 ≤ M ≤ 20,000)

다음 M개의 줄에 걸쳐 두 사람 a와 b, 그리고 두 사람의 촌수 k가 주어진다. (1 ≤ a, b ≤ N, 1 ≤ k ≤ 10)

같은 대화를 여러 번 들을 수도 있으며, 자기 자신과 대화하는 혼잣말을 엿듣는 경우는 없다. (대화 중에 두 사람의 촌수가 변하는 경우는 없다.)

검사 횟수 Q가 주어지고, 다음 Q(1 ≤ Q ≤ 100,000)개의 줄에 촌수를 맞춰야 하는 두 사람 x, y (x≠y)가 주어진다

Q개의 줄에 걸쳐, 각 검사의 정답을 출력한다. 촌수를 알 수 없는 경우에는 -1을 출력한다.