Problem I
Duck Journey

In the local park, there are $N$ ponds, numbered from $1$ to $N$, connected by $M$ channels. The duck Anita has accidentally ended up in a mud puddle, and now all of her $31$ feathers are muddy! Anita is currently in pond $A$, and she wants to get to pond $B$. On the way there, she wants to try to get rid of as much mud as possible. To remove the mud, she can travel through different channels. Each channel has its own filter that will clean specific feathers. This filter is represented by a number which, when translated into base $2$, indicates which feathers are cleaned. For example, a filter with the number $23_{10} = 10111_{2}$ would clean the first, second, third, and fifth feathers. The first feather corresponds to the digit on the rightmost side of the binary number.

Initially, all $31$ feathers are dirty. Your program will receive $Q$ questions, where each question contains two numbers $A$ and $B$. You should answer how many feathers Anita managed to clean after she traveled from pond $A$ to pond $B$, given that she cleaned as many feathers as possible. On the way between the ponds, Anita can travel as she wishes: she can go through the same channel multiple times, and she can visit every pond multiple times (including pond $B$), before deciding she’s done.

If it’s impossible to travel from pond $A$ to pond $B$, you should instead output $-1$.

Input

The first line of input contains the numbers $N$, $M$, and $Q$ ($1 \leq N, Q \leq 10^5$, $1 \leq M \leq 2 \cdot 10^5$), the number of ponds, the number of channels, and the number of questions.

The following $M$ lines describe the channels. The $i$:th line contains the three numbers $a_ i, b_ i,$ and $f_ i$ ($1 \leq a_ i, b_ i \leq N$, $a_ i \neq b_ i$, $0 \leq f_ i \leq 2^{31}-1$). This means that there is a channel between pond $a_ i$ and pond $b_ i$ with a filter value of $f_ i$. It is possible that there are multiple channels between the same pairs of ponds.

Finally, there are $Q$ lines where the $j$:th line contains the numbers $A_ j$ and $B_ j$ ($1 \leq A_ j, B_ J \leq N$), the pond where Anita’s journey starts, respectively ends in question $j$.

Output

Write $Q$ integers, each on their own line: the number of feathers Anita manages to clean after traveling from pond $A_ j$ to pond $B_ j$, given that she chooses a path that removes as much mud as possible. If it’s not possible to travel from pond $A_ j$ to pond $B_ j$, write $-1$ instead.

Scoring

Your solution will be tested on different test groups. To receive points for a group, you must pass all test cases in that group.

Explanation of sample 1:

In question $1$, Anita can visit the following ponds in order: $1,2,3,2$. If she does this, she will clean feathers $1$ and $2$.

In question $2$, Anita can visit pond $4$ and then pond $5$. Then she will have cleaned feathers $1,2,3$ and $4$.

In question $3$, Anita can’t get from pond $1$ to pond $5$.

5 4 3
1 2 1
2 3 2
4 5 7
5 4 8
1 2
4 5
1 5

2
4
-1

3 2 1
1 2 1
3 2 1
1 3

1