În acest episod din Tom&Jerry cele două personaje se urmăresc într-o peşteră. Peştera este formată din N camere (numerotate de la 1 la N), conectate între ele prin M culoare (numerotate de la 1 la M). Fiecare culoar conectează exact două camere. Între două camere este posibil să existe mai multe culoare.
Tom patrulează prin peşteră, parcurgând mereu acelaşi traseu. Traseul lui Tom începe în camera 1 şi se sfârşeşte în camera N. Jerry cunoaşte deja culoarele prin care trece Tom pe traseul său, precum şi timpul necesar lui Tom pentru a parcurge culoarele de pe traseu (mereu acelaşi). Tom nu zăboveşte în camerele peşterii.
Jerry se află iniţial în camera 1 şi doreşte să ajungă în camera N, bineînţeles fără a fi prins de Tom. Jerry se poate deplasa numai pe culoare, el ştiind care este timpul minim în care el poate să parcurgă fiecare culoar. Dacă este necesar, Jerry poate să parcurgă culoarul şi într-un timp mai îndelungat decât timpul minim necesar. În plus, când ajunge într-o cameră, Jerry se poate ascunde şi poate aştepta oricât timp doreşte.
Jerry va fi prins de Tom dacă:
- se află în acelaşi timp pe acelaşi culoar (Jerry va fi prins chiar dacă el intră pe culoar în momentul în care Tom părăseşte culoarul sau, invers, dacă el părăseşte culoarul în momentul în care Tom intră pe culoar);
- dacă intră într-o cameră în momentul în care Tom părăseşte camera sau invers, dacă părăseşte camera în momentul în care Tom ajunge în ea; dacă Jerry este deja în cameră (ascuns) când Tom intră/iese din cameră atunci el nu va fi prins.
Pentru ca Jerry să ajungă în siguranţă în camera N el trebuie prin urmare să nu fie prins de Tom pe traseu şi să ajungă în camera N înaintea lui Tom (pentru a se putea ascunde).
Cerinţă
Scrieţi un program care să verifice dacă Jerry poate ajunge din camera 1 în camera N a peşterii, fără să fie prins de Tom şi dacă da, ce traseu trebuie să urmeze el.
Date de intrare
Fişierul de intrare pestera.in conţine pe prima linie 3 numere naturale separate prin spaţii N M T, reprezentând numărul de camere din peşteră, numărul de culoare din peşteră şi respectiv numărul de culoare de pe traseul parcurs de Tom.
Pe următoarele M linii sunt descrise culoarele peşterii, câte un culoar pe o linie. Pe linia i+1 se află 3 numere naturale separate prin spaţiu X Y S, cu semnificaţia că prin culoarul i Jerry ajunge de la camera X la camera Y în minim S secunde.
Pe următoarele T linii este descris traseul lui Tom, specificând în ordinea parcurgerii culoarele parcurse de Tom, câte un culoar pe o linie. Mai exact, pe fiecare linie dintre cele T sunt scrise două numere naturale separate prin spaţiu C ST, cu semnificaţia că Tom va parcurge întotdeauna culoarul C în ST secunde.
Date de ieşire
Fişierul de ieşire pestera.out va conţine pe prima linie valoarea 1 dacă Jerry poate ajunge din camera 1 în camera N fără a fi prins de Tom, sau valoarea 0, în caz contrar. Dacă pe prima linie a fost scrisă valoarea 1, pe cea de a doua linie va fi scris un număr natural NR, reprezentând numărul de culoare parcurse de către Jerry pe traseul său de la camera 1 la camera N, iar in continuare vor fi scrise NR numere cuprinse între 1 şi M, separate prin spaţii, reprezentând culoarele parcurse de Jerry, în ordinea parcurgerii lor.
Restricţii
- 2 ≤ N ≤ 2000
- 1 ≤ M ≤ 100000
- 1 ≤ T ≤ 100000
- 1 ≤ S, ST ≤ 10000
- Culoarele peşterii pot fi parcurse în ambele sensuri.
Exemple
| pestera.in |
pestera.out |
4 4 5
1 3 6
1 2 2
2 3 2
3 4 1
2 1
2 2
2 1
3 4
4 1
|
1
2 1 4
|