Galaxia

Civilizația avansată a moisiliștilor trăiește în Galaxia G. care este compusă din $N$ corpuri cerești, numerotate de la $1$ la $N$. Acestea sunt de două tipuri: planete și sateliți, fiecare corp având atribuită o gravitație ($G_{i}$). Între două corpuri cerești poate exista un lift care face posibilă deplasarea între ele. Energia necesară deplasării cu liftul între două corpuri, $i$ și $j$, este calculată astfel:

• Dacă ambele corpuri sunt planete, costul energetic este egal cu valoarea celui mai mic multiplu comun al gravitațiilor acestora ( $cmmmc(G_{i}, G_{j})$ );
• Dacă un corp este o planetă iar celălalt este un satelit, costul energetic este egal cu valoarea celui mai mare divizor comun între gravitațiile acestora ( $cmmdc(G_{i}, G_{j})$ );
• Între doi sateliți, costul energetic va fi mereu $1$.

Tragic, o planetă a fost infectată cu un virus foarte contagios. Dacă o planetă $i$ este infectată, atunci toate planetele conectate printr-un lift vor fi, la rândul lor, infectate după o zi de la infectarea planetei $i$ (dacă nu sunt deja infectate). Din fericire, sateliții nu pot fi infectați și nici nu pot răspândi virusul, aceștia nefiind suficient de populați. Prin urmare, regina Galaxiei G. alege o planetă drept refugiu și își dorește să afle constul energetic minim necesar pentru a se deplasa de la aceasta la orice altă planetă.

Cerințe

Regina, fiind ocupată cu alte lucruri, îi porunceste lui Rareș, moisilian priceput, să afle:

1. Fiind specificată planeta $K$ din care începe răspandirea infecției în ziua $1$, după câte zile vor fi infectate celelalte planete?
2. Fiind aleasă planeta $K$ ca refugiu de către regină, care este costul energetic minim necesar pentru a ajunge de la planeta $K$ la oricare altă planetă?

Date de intrare

În fișierul de intrare galaxia.in avem:

• Prima linie conține numărul $C$, care va avea valoarea $1$, respectiv $2$, indicând cerința care trebuie rezolvată
• A doua linie conține numerele $N$ și $M$, care reprezintă numărul de corpuri cerești, respectiv numărul de lifturi dintre corpuri;
• Pe următoarele $N$ linii se dau câte două numere, $T_{i}$ și $G_{i}$, care reprezintă tipul corpului ceresc $i$ ($1$ pentru planetă, $0$ pentru satelit) și gravitația acestuia (pe linia $i + 2$ se găsesc tipul și gravitația corpului $i$);
• Pe următoarele $M$ linii se regasesc câte două numere, $A$ și $B$, semnificând că exista un lift între corpurile $A$ și $B$;
• Pe ultima linie se dă valoarea $K$, care reprezintă:
  • Indicele planetei de la care începe infecția, dacă $C=1$;
  • Indicele planetei alese de regină drept refugiu, dacă $C=2$.

Date de ieșire

În fișierul de ieșire galaxia.out avem:

• Dacă $C=1$, se va afișa mai întâi $N_{p}$, numărul de planete, și pe următoarele $N_{p}$ linii se vor afișa, cu spațiu între ele, $i$ și $T_{i}$, semnificând că planeta $i$ va fi infectată după $T_{i}$ zile. (în cazul în care planeta nu va fi infectată niciodată, $T_{i} = -1$);
• Dacă $C=2$, se va afișa mai întai $N_{p}$, numărul de planete, și pe următoarele $N_{p}$ linii se vor afișa, cu spațiu între ele, $i$ si $E_{i}$, semnificând că, pentru a ajunge la planeta $i$, costul energetic minim necesar este $E_{i}$ (dacă $K = i$, $E_{i} = 0$).

Restricții și precizări

• Pentru ambele cerințe, planetele trebuiesc afișate în ordine crescătoare
• $C \in \{1, 2\}$
• $1 \le N \le 50 \ 000$
• Se dă cel puțin o planetă ($N_{p} \ge 1$)
• $0 \le M \le 300 \ 000$
• $T_{i} \in \{0, 1\}; 1 \le G_{i} \le 1 \ 000 \ 000$, unde $1 \le i \le N$
• $1\le K \le N$
• Corpul cerest cu indicele $K$ va fi întotdeauna planetă.
• Putem să ne deplasăm de la oricare corp ceresc $A$ la oricare corp $B$, cu condiția $A ≠ B$

Exemplul 1

galaxia.in

1
9 13
0 5
1 8
1 2
0 7
0 9
1 10
0 3
1 20
1 14
1 2
1 3
1 4
2 4
3 5
3 7
4 5
4 6
4 8
4 9
5 8
6 7
6 8
6

galaxia.out

5
2 -1
3 -1
6 1
8 2
9 -1

Exemplul 2

galaxia.in

2
9 13
0 5
1 8
1 2
0 7
0 9
1 10
0 3
1 20
1 14
1 2
1 3
1 4
2 4
3 5
3 7
4 5
4 6
4 8
4 9
5 8
6 7
6 8
6

galaxia.out

5
2 2
3 2
6 0
8 2
9 8

Explicație

• Corpurile verzi cu numărul în bold sunt planetele iar corpurile roșii cu numărul în italic sunt sateliții; în imagine sunt evidențiate costurile energetice între corpurile cerești.

În primul exemplu cerința este $1$ și $6$ este infectată în ziua $1$. Doar planeta $8$ este conectată de planeta $6$, deci planeta $8$ va fi infectată in ziua $2$. Infecția nu ajunge la celelalte planete deoarece planetele $6$ și $8$ sunt izolate de ele prin sateliții $4$, $5$ și $7$.

În al doilea exemplu cerința este $2$ deci trebuie să aflăm costul de energie minim necesar pentru a ajunge de la fiecare planetă la planeta $6$. Astfel, drumul $2→4→6$ are costul $2$, drumul $3→7→6$ are costul $2$, drumul $8→4→6$ are costul $2$ și drumul $9→4→6$ are costul $8$.