Baegyang Road Break

Y University in Seoul started a large construction project, and the campus turned into a maze. Before the work began you could walk from any building to every other building. After it started, for reasons nobody can explain, the number of roads that go only one way grew a lot.

Namgyu, a computer science student, got lost on his way from a major class to an elective. After three days and nights of wandering he concluded that there is no route at all from the Engineering Hall to the Main Hall.

Three days of missed assignments and missed attendance put Namgyu one step from academic probation, so he decided to put his major to work. He would find out how many of the current one-way roads must be turned into two-way roads, then bring the result to the university.

Namgyu surveyed every road that directly connects two buildings and wrote down which ones are one-way and which ones are two-way.

His program is simple. You give it a start and a destination, and it reports the smallest number of roads that must be turned into two-way roads to get there. Word spread that the program was finished, and students who had been lost themselves started asking Namgyu questions.

"Can I get from the Engineering Hall to the Auditorium?"

"What about from the Business Annex to the Student Union?"

Namgyu wore himself out typing each question in by hand and sending the answer back, and he ended up sick in bed. Write the program that answers all of the students' questions for him at once.

The first line has the number of buildings $n$ and the number of roads $m$ at Y University. ($1 \le n \le 250$, $0 \le m \le n(n-1)/2$)

Each of the next $m$ lines describes one road as $u$ $v$ $b$. ($1 \le u \le n$, $1 \le v \le n$, $u \ne v$, $b$ is 0 or 1)

If $b$ is 0, the road is one-way and can only be walked from $u$ to $v$. If $b$ is 1, the road between $u$ and $v$ can be walked in both directions.

At most one road directly connects any two buildings.

The next line has the number of student questions $k$. ($1 \le k \le 30000$)

Each of the next $k$ lines holds one question as $s$ $e$. ($1 \le s \le n$, $1 \le e \le n$) The student who asked wants to go from building $s$ to building $e$.

Print $k$ lines.

For each question, print on its own line the smallest number of one-way roads that must be turned into two-way roads so that you can walk from building $s$ to building $e$. The roads you turn are counted separately for every question. Roads turned for an earlier question have no effect on a later one.

If every road is turned into a two-way road, no pair of buildings is unreachable from each other.