Problem A
Jaga råttor

Förra året lyckades ingen jaga ut jätteråttorna ur Göteborg (se problemet KATT och råtta¹). På grund av detta har Olle inget annat val än att ta saken i egna händer och själv jaga in alla Göteborgs råttor i fällor.

Göteborgs kloaker består av $N$ brunnar, och det finns $M$ rör som kopplar samman par av brunnar. När Olle ska jaga en råtta sätter han en fälla i brunn $T$. Han börjar sedan i brunn $S$ och råttan börjar i brunn $R$. Målet är att få råttan att gå in i fällan i brunn $T$. Olle kan förflytta sig mellan brunnarna med hjälp av rören. Om han går in i samma brunn som råttan, så kommer den fly till en intilliggande brunn. Efter att ha jagat många råttor har han märkt att de är förutsägbara: om han går in i en brunn från ett visst rör, så kommer råttan alltid att fly till en särskild brunn.

Olle har tyvärr märkt att vissa råttor inte går att fånga. Han vill därför ha din hjälp $Q$ gånger att avgöra om det går att fånga råtten givet $S$, $R$ och $T$. Alla frågor är oberoende varandra, och det finns alltid exakt en råtta i kloakerna per fråga.

Indata

Den första raden i indatan innehåller heltalen $N$, $M$ och $Q$ ($3 \leq N \leq 10^5$, $1 \le M,Q \le 10^5$), antalet brunnar, antalet rör och antalet frågor.

De följande $M$ raderna beskriver vardera ett rör. Varje rör beskrivs av heltalen $u$, $v$, $a$, $b$ ($1 \leq u,v,a,b \leq N$, $u \neq v$, $1 \leq a,b \leq N$), där $u$, $v$ beskriver att det finns ett rör mellan brunn $u$ och $v$. $a$ beskriver att om Olle färdas från $u$ till $v$ och en råtta befinner sig i brunn $v$, så kommer den fly till brunn $a$. $b$ beskriver motsvarande att om Olle befinner sig i brunn $v$ och färdas till $u$, så flyr råtten till brunn $b$. Det är även garanterat att det finns som mest ett rör mellan varje par av brunnar, röret $(v,a)$ finns och röret $(u,b)$ finns. Det är också garanterat att Olle kan ta sig från varje brunn till alla andra brunnar.

Därefter följer $Q$ rader som vardera innehåller heltalen $S$, $R$, $T$ ($1 \leq S,R,T \leq N$), som beskriver att Olle undrar om han kan jaga råttan i brunn $R$ till brunn $T$ om han börjar på brunn $S$. Det är garanterat att $T \neq S$, $T \neq R$ och $S \neq R$.

Notera att detta problemet har väldigt mycket indata. Det är därför rekommenderat att använda snabb indataläsning.

Utdata

Svara på varje fråga i samma ordning som i indatan. Om Olle kan jaga in råttan i fällen, skriv ut 1, annars 0.

Poängsättning

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

Låt $deg(u)$ vara antalet rör som brunn $u$ är sammankoplad med.

Förklaring av exempelfall 1

Brunnarna är sammankopplade som följande. Råttans flyktvägar är inte ritade så att det inte blir rörigt.

• Fråga 1: Det finns ingen flyktväg för råttan som leder till brunn 4. Därmed är svaret nej.

• Fråga 2: Olle kan jaga in råttan i fällan direkt.

• Fråga 3: Hur Olle än jagar råttan kan han aldrig ta sig till brunn 4 samtidigt som råttan befinner sig i brunn 1. Därmed är svaret nej.

5 5 3
1 2 1 2
2 3 1 1
3 1 3 1
4 1 5 1
5 1 3 1
2 1 4
4 1 5
2 1 5

0
1
0