17246번 - 씨씨 채점 준비 중

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

하지만 누군가에게는 고통스러운 날이다. 성씨가 씨이고 이름이 씨인 '씨씨'는 모임이 끝나면 '씨'씨 혈통의 족보를 완성해야하기 때문이다. 
'씨'씨 혈통의 모든 사람들은 시크릿하기 때문에 자신을 직접 소개하기를 무척 꺼려한다. 족보를 완성해야만 하는 '씨씨'는 총 M개의 대화를 엿들어 두 사람이 부르는 호칭을 듣고 그 촌수를 알아낼 수 있었다. 

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

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

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

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

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

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

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