== include(page="template/taskheader" task_id="marmelada") ==

Poveste şi cerinţă...

Primarul judetului Marmelada trebuie sa refaca in totalitate reteaua stradala. In judet exista $N$ orase numerotate cu numere naturale de la $1$ la $N$. Se mai si stiu cele $M$ sosele care trebuie construite, o sosea leaga direct doua orase si se poate circula pe ambele sensuri. Primarul trebuie sa decida acum ce lungime sa aibe fiecare sosea. Firma de constructii s-a oferit sa construiasca $M$ sosele de lungimi $C{~1~}, C{~2~} ... C{~M~}$ si i-a lasat libertatea primarului de a decide pentru fiecare sosea din judet ce lungime sa aibe (altfel spus trebuie realizata o bijectie intre multimea de lungimi si multimea de sosele). Primarul are doua orase preferate, $S$ si $D$ si doreste ca dupa construirea soselor sa existe cel mai scurt drum posibil intre cele doua orase. Un drum este o succesiune de sosele astfel incat oricare doua sosele consecutive au un oras in comun. Ajutati primarul orasului si determinati pentru fiecare sosea ce leaga doua orase ce lungime trebuie sa aibe ea.

h2. Date de intrare

Fişierul de intrare $marmelada.in$ ...

Fişierul de intrare $marmelada.in$ contine pe prima linie patru numere naturale separate de un spatiu, $N$, $M$, $S$ si $D$, avand semnificatia din enunt. Urmeaza apoi $M$ linii, fiecare linie continand doua numere separate de un singur spatiu $a$ si $b$ avand semnificatia ca trebuie construita o sosea intre orasele $a$ si $b$. Pe linia $M+1$ din fisier se afla $M$ numere naturale $C{~1~}, C{~2~} ... C{~M~}$, avand semnificatia din enunt.

h2. Date de ieşire

În fişierul de ieşire $marmelada.out$ ...

În fişierul de ieşire $marmelada.out$ se vor afisa $M$ numere naturale cuprinse intre $1$ si $M$ (fiecare numar pe cate o linie). Daca al $i$-lea numar din fiser este $j$ inseamna ca soseaua avand indicele $i$ (soselele sunt numerotate de la $1$ la $M$ in ordinea in care apar in fisierul de intrare) i-a fost atribuita lungimea $C{~j~}$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N, M ≤ 100 000$
* Lungimile soselelor sunt numere naturale mai mici decat $10 000$

h2. Exemplu
table(example). |_. marmelada.in |_. marmelada.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 4 1 4
  1 2
  2 4
  1 3
  3 4
  1 1 2 2
| 1
  2
  3
  4

|
h3. Explicaţie

...

Soseaua $1-2$ si $2-4$ au lungimea $1$, deci exista un drum de lungime $2$ intre orasele $1$ si $4$. Acesta este cel mai mic drum posibil dintre toate care s-ar putea fi obtinut.

== include(page="template/taskfooter" task_id="marmelada") ==