Castel

Unui muncitor i se încredinţează o grea misiune. El are de lăcuit toate coridoarele unui castel. Pentru aceasta el primeşte o hartă în care sunt reprezentate coridoarele şi cele $N$ puncte de intersecţie ale acestora (numerotate de la $1$ la $N$). Unele puncte de intersecţie sunt considerate de muncitor ca fiind “puncte speciale” deoarece ele sunt singurele puncte care îi permit ieşirea şi intrarea în castel, prin intermediul unor uşi.

Deoarece operaţia de lăcuire trebuie să fie efectuată în cel mai scurt timp, muncitorului i s-a impus ca orice coridor să nu fie traversat decât o singură dată, adică doar atunci când este lăcuit. În aceste condiţii, muncitorul trebuie să lăcuiască toate coridoarele, folosindu-se eventual de “punctele speciale” ale castelului, plecând din orice intersecţie de coridoare doreşte şi terminând operaţia în acelaşi punct.

Cerinţa:

Determinaţi un traseu ciclic prin care operaţia este satisfăcută.

Date de intrare

Fișierul de intrare castel.in conține pe următoarele linii:

• Pe prima linie numărul $N$.
• Pe a doua linie numărul de coridoare $M$.
• Pe următoarele $M$ linii perechi de două numere reprezentând perechi de puncte între care există coridor ce trebuie lăcuit.
• Pe următoarea linie numărul $P$ reprezentând numărul de “puncte speciale”.
• Pe ultima linie şirul “punctelor speciale” separate prin câte un spaţiu.

Date de ieșire

Ieşirea se va face în fişierul castel.out în formatul următor: Pe prima linie se va scrie mesajul DA sau NU, după cum există sau nu un traseu ciclic care respectă cerinţele. În caz afirmativ fişierul va conţine pe a doua linie un şir de numere reprezentând punctele în ordinea de apariţie pe traseu, despărţite după caz de secvenţa de caractere - (spaţiu minus spaţiu) sau * (spaţiu asterisc spaţiu).

O secvenţă de tipul $i$ - $j$ semnifică faptul că muncitorul a traversat şi lăcuit coridorul dintre punctele $i$ şi $j$.

O secvenţă de tipul $i$ * $j$ semnifică faptul că muncitorul a părăsit castelul prin “punctul special” $i$ şi a revenit în castel prin “punctul special” $j$.

Restricții și precizări

• $1 \leq N \leq 5 \ 000$;
• $1 \leq M \leq 10 \ 000$;
• Jumătate din testele folosite pentru evaluare vor avea dimensiunea $N \leq 100$;
• Dacă există mai multe soluții, se va afișa oricare dintre ele.

Exemplul 1

castel.in

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

castel.out

DA
1 – 2 - 5 * 6 - 4 - 3 - 2 * 4 – 1