- Time limit: 1.00 s
- Memory limit: 128 MB
Kaaleppi on tällä hetkellä kaupungissa ja haluaa siirtyä kaupunkiin . Tiedossasi on kaikki seudun kaupungit ja niiden väliset tiet.
Asiassa on kuitenkin yksi ongelma: Kaaleppi on etsintäkuulutettu kaupungissa . Tehtäväsi onkin selvittää, onko olemassa reittiä kaupungista kaupunkiin kulkematta kaupungin kautta.
Lisähaasteena sinun pitää käsitellä suuri määrä tällaisia kyselyitä annetussa kaupunkiverkossa.
Syöte
Syötteen ensimmäisellä rivillä on kolme kokonaislukua , ja : kaupunkien määrä, teiden määrä ja kyselyiden määrä. Kaupungit on numeroitu .
Sitten syötteessä on riviä, joista kullakin on kaksi kokonaislukua ja : kaupunkien ja välillä on tie. Kaikki tiet ovat kaksisuuntaisia, eikä mistään kaupungista ole tietä itseensä.
Lopuksi syötteessä on riviä, joista kullakin on kolme kokonaislukua , ja : pääseekö kaupungista kaupunkiin kulkematta kaupungin kautta?
Voit olettaa, että minkä tahansa kahden kaupungin välillä on olemassa jokin reitti.
Tuloste
Tulosta jokaiseen kyselyyn "10-4", jos reitti on mahdollinen, ja muuten "QAQ".
Rajat
Esimerkki
Syöte:
5 6 3 1 2 1 3 2 3 2 4 3 4 4 5 1 4 2 3 5 4 3 5 2
Tuloste:
10-4 QAQ 10-4