Swiss Olympiad in Informatics

Maus Stofl besucht wieder einmal seine Freunde in der unterirdischen Mäusestadt genannt Underground City.
Viele Mäuse leben in dieser Stadt. Jede Mäusefamilie hat ihr eigenes unterirdisches Mauseloch. Diese Mauselöcher sind durch unterirdische Tunnels verbunden, die in beide Richtungen begangen werden können.
Leider kann man durch diese Tunnel nicht von jedem Mauseloch jedes andere erreichen. Da Stofl so viele Freunde hat und häufig zu Ihnen reist, möchte er wissen, von welchen Freunden aus er welche erreichen kann, damit er die Reihenfolge, in der er seine Freunde besucht, optimieren kann. Deshalb stellt er dir Fragen der Form: Ist A von B aus durch die unterirdischen Tunnel erreichbar? Du musst alle diese Fragen beantworten.

Du kennst alle Tunnel, die die Mauslöcher miteinander verbinden. Für jede Frage in der oben angegebenen Form musst du entscheiden, ob eine Verbindung zwischen den beiden genannten Löchern besteht.

Die erste Zeile des Inputs enthält drei ganze Zahlen L, M und N (1 ≤ L ≤ 10'000, 1 ≤ M,N ≤ 200'000), die Anzahl Mauselöcher in Underground City, nummeriert von 1 bis L, die Anzahl Tunnels zwischen diesen Löchern und die Anzahl Fragen, die du beantworten musst.

Es folgen M Zeilen, die die Tunnels im Format «s_j e_j» (1 ≤ s_j, e_j ≤ L), beschrieben, wobei s_j und e_j die Löcher bezeichnen, bei denen Tunnel j startet bzw. endet.

Die folgenden N Zeilen enthalten je zwei Zahlen a_k und b_k. Diese entsprechen Stofls Frage, ob eine Verbindung zwischen den Mauselöchern mit den Indizes a_k und b_k besteht.

Gib für jede der N Fragen die Antwort als einzelnes Zeichen aus: 'Y', falls das Loch b_k von Loch a_k aus durch die Tunnel von Underground City erreicht werden kann, und 'N', falls nicht (ohne die Anführungszeichen). Alle Antworten sollen auf einer Zeile stehen, jeweils durch ein Leerzeichen getrennt.

6 7 5
1 2
2 3
1 2
1 6
1 3
5 4
3 2
1 2
3 4
2 5
2 3
2 6

Y N N Y Y

7 5 1
1 3
2 3
5 2
4 5
4 6
1 6

Y

• Zweite Beispieleingabe/-ausgabe hinzugefügt um Aufgabe zu verdeutlichen
• Um Mauseloch A von Mauseloch B aus zu erreichen, ist es egal wie viele andere Mauselöcher zwischendrin besucht werden. Selbst wenn alle anderen Mauselöcher besucht werden müssen, gelten A und B als verbunden. Siehe dazu die zweite Beispieleingabe.

Submission form