Is There a Path

Citește un graf și două dintre nodurile lui, s și t, și afișează true dacă poți ajunge de la s la t mergând pe muchii, false dacă nu poți. Un nod poate ajunge mereu la el însuși.

Cum se scrie un graf

Pe prima linie sunt numărul de noduri n și numărul de muchii m. Urmează m linii, câte una pentru fiecare muchie, cu cele două noduri pe care le unește. Nodurile sunt numerotate de la 0 la n - 1, iar o muchie merge în ambele sensuri.

0 --- 1 --- 2     3 --- 4     5

Graful acesta se scrie:

6 3
0 1
1 2
3 4

Nodul 5 nu are nicio muchie, așa că apare doar în numărul 6.

Codul de început citește deja graful în vecini, unde vecini[u] are vecinii lui u, apoi afișează true sau false după ce întoarce exista_drum. Tu scrii exista_drum.

Date de intrare

• Linia 1: n și m. Sunt între 1 și 500 de noduri și cel mult 2000 de muchii.
• Următoarele m linii: muchiile. Nicio muchie nu unește un nod cu el însuși și nicio pereche de noduri nu e unită de două muchii.
• Ultima linie: s și t.

Rezultat

true dacă există un drum de la s la t, altfel false.

Exemple

Intrare:
6 3
0 1
1 2
3 4
0 2

Ieșire:
true

De la 0 la 1, apoi de la 1 la 2.

Intrare:
6 3
0 1
1 2
3 4
2 4

Ieșire:
false

Nicio muchie nu iese din bucata 0, 1, 2, așa că de la 2 nu se ajunge la 4.

Intrare:
6 3
0 1
1 2
3 4
5 5

Ieșire:
true

5 nu are nicio muchie, dar e deja acolo unde trebuie să ajungă.