genius

Time limit: 0.1s Memory limit: 64MB Input: genius.in Output: genius.out

La grupa de excelență la care profesorul Genius predă sunt înscriși NN elevi (reprezentați prin numere distincte de la 11 la NN) care sunt sau nu prieteni. Pentru a face rezolvatul de probleme mai interesant, profesorul a inventat un joc: acesta alege elevul cu indicele KK și îi spune enunțul unei probleme la care să se gândească și pe care să o spună mai departe tuturor prietenilor săi. Fiecare elev care află problema o va transmite în ziua următoare prietenilor săi care nu au aflat-o încă și tot așa, până când problema nu mai poate fi transmisă mai departe. Jocul e însă mai complex de atât: în ziua în care un elev află problema nivelul său de aprofundare a problemei este 00, în următoare zi nivelul de aprofundare este 11 și așa mai departe. În ziua XX după aflarea problemei, un elev va ajunge la gradul XX de aprofundare al acesteia. Profesorul Genius i-a anunțat pe elevi că aceștia se vor întâlni pentru a rezolva problema doar după ce toată lumea a aflat problema și toți elevii au ajuns la un nivel de aprofundare al problemei cel puțin PP.

Cerință

Știind modul în care funcționează jocul, profesorul Genius vrea să calculeze după câte zile de la lansarea problemei se va întâlni cu elevii săi pentru a o rezolva.

Date de intrare

Fișierul de intrare genius.in conține următoarele informații:

  • pe prima linie se află două numere: NN, numărul de elevi înscriși la grupa de excelență, și MM, numărul relațiilor de prietenie;
  • pe următoarele M linii se află câte două numere AA și BB, acestea reprezentând o relație de prietenie (bidirecțională) între elevii desemnați de cele două numere;
  • pe următoarea linie se află KK, indicele elevului căruia profesorul îi spune prima dată problema;
  • pe următoarea linie se află PP, nivelul minim de aprofundare al problemei de către toți elevii, necesar pentru ca elevii să se întâlnească pentru aflarea rezolvării.

Date de ieșire

În fișierul genius.out se va afișa un singur număr natural, reprezentând numărul minim de zile după care elevii se vor întâlni cu profesorul Genius pentru rezolvarea problemei sau 1-1 dacă întâlnirea nu este posibilă în condițiile impuse de joc.

Restricții și precizări

  • 2N50 0002 \leq N ≤ 50 \ 000
  • 1M100 0001 \leq M ≤ 100 \ 000
  • 1A,BN1 \leq A, B \leq N
  • 1KN1 \leq K \leq N
  • 1P10 000 0001 \leq P \leq 10 \ 000 \ 000

Exemplu

genius.in

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

genius.out

8

Explicație

  • În ziua 00, elevul 22 află problema și are nivelul de aprofundare 00;
  • În ziua 11, află problema elevii cu indicii 44 și 55;
  • În ziua 22, află problema elevii cu indicii 11 și 66;
  • În ziua 33, află problema elevii cu indicii 33 și 77.

Au trecut 33 zile și pentru ca nivelul minim de aprofundare pentru oricare dintre elevi să fie 55, trebuie să mai treacă încă 55 zile.

Log in or sign up to be able to send submissions!