Problem D
Andväg

I den lokala parken finns det $N$ stycken dammar, numrerade från $1$ till $N$, som förbinds av $M$ kanaler. Anden Anita har råkat hamna i en gyttjepöl, och nu är alla hennes $31$ fjädrar leriga! Anita befinner sig nu i damm $A$, och vill ta sig till damm $B$. På vägen däremellan vill hon försöka bli av med så mycket lera som möjligt. För att få bort leran kan hon åka genom olika kanaler. Kanalerna har alla var sitt filter som kommer att rengöra vissa specifika fjädrar. Detta filtret representeras av ett tal som, om vi översätter det till bas $2$, berättar vilka fjädrar som rengörs. Till exempel skulle ett filter med talet $23_{10} = 10111_{2}$ göra att den första, andra, tredje och femte fjädern rengjordes. Den första fjädern motsvaras av den siffra som står längst till höger i det binära talet.

Från början är alla $31$ fjädrar smutsiga. Ditt program kommer att få $Q$ stycken frågor, där varje fråga innehåller två tal $A$ och $B$. Du ska svara på hur många fjädrar som Anita lyckats städa efter att hon tagit sig från damm $A$ till damm $B$ om hon städar så många som möjligt. På vägen mellan dammarna får Anita färdas hur hon vill: Hon får åka över samma kanal flera gånger, och hon får besöka varje damm (inklusive damm $B$) flera gånger innan hon bestämmer sig för att vara färdig.

Om det är omöjligt att färdas från damm $A$ till damm $B$ ska du skriva ut $-1$.

Indata

Den första raden i indatan innehåller heltalen $N$, $M$ och $Q$ ($1 \leq N, Q \leq 10^5$, $1 \leq M \leq 2 \cdot 10^5$), antalet dammar, antalet kanaler och antalet frågor.

Därefter följer $M$ rader som beskriver kanalerna. Den $i$:te raden innehåller de tre talen $a_ i, b_ i$ och $f_ i$ ($1 \leq a_ i, b_ i \leq N$, $a_ i \neq b_ i$, $0 \leq f_ i \leq 2^{31}-1$). Det betyder att det går en kanal från damm $a_ i$ till damm $b_ i$ med filtervärde $f_ i$. Det är möjligt att det går flera kanaler mellan samma par av dammar.

Slutligen följer $Q$ rader där den $j$:te raden innehåller talen $A_ j$ och $B_ j$ ($1 \leq A_ j, B_ J \leq N$), dammen där Anitas färd ska startas respektive sluta i den $j$:te frågan.

Utdata

Skriv ut $Q$ heltal på varsinn rad: Antalet fjädrar som Anita lyckas tvätta efter att ha tagit sig från damm $A_ j$ till damm $B_ j$, givet att hon väljer en väg som får bort så mycket lera som möjligt. Om det inte går att ta sig från damm $A_ j$ till damm $B_ j$ ska du istället skriva $-1$.

Poängsättning

Din lösning kommer att testas på olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall 1:

I fråga $1$ kan Anita besöka följande dammar i ordning: $1,2,3,2$. Om hon gör detta kommer hon att städa fjädrar $1$ och $2$.

I fråga $2$ kan Anita besöka damm $4$ och sen damm $5$. Då kommer hon att städa fjädrar $1,2,3$ och $4$.

I fråga $3$ kan Anita inte ta sig från damm $1$ till damm $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