Obiective

obiective

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

Intr-un oras mai ciudat exista $N$ intersectii si $M$ strazi unidirectionale ( sens unic ) intre aceste intersectii. Aceasta inseamna ca de la o intersectie la alta intre care exista strada nu se poate circula decat in unul din cele doua sensuri posibile. Analizand mai atent harta strazilor din oras, politia locala a ajuns la concluzia ca din unele intersectii nu se poate ajunge in alte intersectii mergand pe strazi doar in sensul lor de parcurgere. Primaria orasului doreste sa construiasca o gara noua si un muzeu care va atrage numerosi turisti. Amplasamentele cladirilor se vor afla in doua intersectii diferite. Datorita sistemului stradal lucrurile sunt complicate, deoarece exista posibilitatea ca turistii care au ajuns la gara sa nu poata, luand un taxi spre exemplu, ajunge la intersectia unde se afla muzeul, si, de aceea, politia va trebui sa schimbe orientarea unor strazi pentru a face acest lucru posibil.

Intr-un oras mai ciudat exista $N$ intersectii si $M$ strazi unidirectionale ( sens unic ) intre aceste intersectii. Aceasta inseamna ca de la o intersectie la alta intre care exista strada nu se poate circula decat in unul din cele doua sensuri posibile. Analizand mai atent harta strazilor din oras, politia locala a ajuns la concluzia ca din unele intersectii nu se poate ajunge in alte intersectii mergand pe strazi doar in sensul lor de parcurgere. Primaria orasului doreste sa construiasca o gara noua si un muzeu care va atrage numerosi turisti. Amplasamentele cladirilor se vor afla in doua intersectii diferite. Datorita sistemului stradal lucrurile sunt complicate, deoarece exista posibilitatea ca turistii care au ajuns la gara sa nu poata, luand un taxi spre exemplu, ajunge la intersectia unde se afla muzeul, si, de aceea politia va trebui sa schimbe orientarea unor strazi pentru a face acest lucru posibil.

Firma care va construi atat muzeul cat si gara pune la dispozitia primariei $T$ oferte, prin care se specifica locatia ambelor constructii. Pentru fiecare oferta primaria trebuie sa identifice care este numarul minim de strazi carora trebuie sa le schimbe orientarea pentru ca turistii sa poata ajunge de la gara la muzeu.
h2. Date de intrare

h2. Date de iesire

Datele de iesire se afiseaza in fisierul {$obiective.out$}. Pe linia $i$ din acest fisier se afla numarul minim de strazi care trebuiesc reorientate pentru a exista cel putin un drum de la gara la muzeu, conform amplasarii acestor cladiri din a {$i$}-a oferta din fisierul de intrare.

Datele de iesire se afiseaza in fisierul {$obiective.out$}. Pe linia $i$ din acest fisier se afla numarul minim de strazi care trebuiesc reorientate pentru a exista cel putin un drum de la gara la muzeu, conform constructiei acestor cladiri din oferta a {$i$}-a din fisierul de intrare.

h2. Restrictii

* $5 ≤ M ≤ 64 000$
* $1 ≤ T ≤ 100 000$
* Pentru orientarea initiala a strazilor, se garanteaza ca oricum am alege 3 intersectii {$A$}, {$B$}, {$C$}, astfel incat sa putem ajunge din $A$ in $C$ si din $B$ in {$C$}, atunci putem ajunge fie din {$A$} in {$B$}, fie din {$B$} in {$A$} ( posibil ambele )

* Daca se ignora orientarea strazilor, se poate ajunge din orice intersectie in oricare alta

* Intre oricare doua intersectii exista cel mult o strada

* Pentru 30% din teste, raspunsul pentru fiecare oferta nu va depasi $10$

h2. Exemplu

2 4
4 5
3 4

3

2

4 3
5 1

1 5

|1
2

0

|
h3. Explicatie

Pentru a doua oferta, putem redirectiona strazile {$4->5$} si {$2->4$} pentru a putea ajunge din intersectia $5$ in intersectia {$1$}.

Pentru a doua oferta, putem redirectiona strazile 4->5 si 2->4 pentru a putea ajunge din intersectia $5$ in intersectia {$1$}.

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

...
== include(page="template/taskfooter" task_id="obiective") ==

1953