백양로 브레이크

서울에 있는 Y 대학교가 대규모 공사에 들어가면서 캠퍼스가 미로처럼 변했다. 공사 전에는 어느 건물에서 출발해도 나머지 모든 건물로 갈 수 있었는데, 공사가 시작된 뒤로는 어찌 된 일인지 한쪽 방향으로만 다닐 수 있는 길이 크게 늘었다.

컴퓨터과학과 학생 남규는 전공 수업을 마치고 교양 수업을 들으러 가다가 길을 잃었다. 사흘 밤낮을 헤맨 끝에 공학관에서 종합관으로 가는 길이 아예 없다는 결론을 내렸다.

사흘 동안 과제도 내지 못하고 출석도 하지 못해 학사경고를 받을 처지가 된 남규는 전공을 살리기로 했다. 지금 일방통행인 길 가운데 반드시 양방향으로 바꿔야 하는 길이 몇 개인지 조사해서 학교에 건의할 생각이다.

남규는 건물 사이를 직접 잇는 길을 모두 조사해 어떤 길이 일방통행이고 어떤 길이 양방향인지 기록했다.

남규가 만든 프로그램은 단순하다. 출발지와 도착지를 넣으면 도착지까지 가기 위해 최소 몇 개의 길을 양방향으로 바꿔야 하는지 알려준다. 프로그램이 완성됐다는 소문이 퍼지자 길을 잃어 본 학생들이 남규에게 묻기 시작했다.

"공학관에서 대강당 갈 수 있어?"

"상경대 별관에서 학관으로는?"

질문을 하나씩 손으로 입력하고 답을 돌려주다 지친 남규는 결국 앓아누웠다. 남규 대신 학생들의 질문을 한꺼번에 처리하는 프로그램을 만들어 보자.

첫 줄에 Y 대학교 건물의 수 $n$과 길의 수 $m$이 주어진다. ($1 \le n \le 250$, $0 \le m \le n(n-1)/2$)

다음 $m$개 줄에는 길 하나의 정보가 $u$ $v$ $b$ 형태로 주어진다. ($1 \le u \le n$, $1 \le v \le n$, $u \ne v$, $b$는 0 또는 1)

$b$가 0이면 $u$에서 $v$로만 갈 수 있는 일방통행 길이고, $b$가 1이면 $u$와 $v$를 양쪽으로 다닐 수 있는 길이다.

두 건물을 직접 잇는 길은 많아야 하나다.

다음 줄에 학생들의 질문 수 $k$가 주어진다. ($1 \le k \le 30000$)

다음 $k$개 줄에는 질문이 $s$ $e$ 형태로 주어진다. ($1 \le s \le n$, $1 \le e \le n$) 질문한 학생이 건물 $s$에서 건물 $e$로 가고 싶다는 뜻이다.

$k$개 줄을 출력한다.

각 질문마다 건물 $s$에서 건물 $e$로 가려면 일방통행인 길을 최소 몇 개 양방향으로 바꿔야 하는지 한 줄에 하나씩 출력한다. 길을 바꾸는 일은 질문마다 따로 센다. 앞선 질문에서 바꾼 길은 다음 질문에 영향을 주지 않는다.

모든 길을 양방향으로 바꾸면 서로 오갈 수 없는 건물 쌍은 없다.