Fie un număr natural $N$. Se numeşte DivisorGraph al numărului $N$, un graf orientat cu $NrDivizori(N)$ noduri obţinut după cum urmează:
1. Fiecărui divizor al lui $N$ i se asociază un nod unic. De-asemenea, fiecare nod are asociat un unic divizor al lui $N$. Cu alte cuvinte, există o bijecţie între divizorii lui $N$ şi nodurile grafului.
1. Fiecărui divizor al lui $N$ i se asociază exact un nod. De-asemenea, fiecare nod are asociat exact un divizor al lui $N$. Cu alte cuvinte, există o bijecţie între divizorii lui $N$ şi nodurile grafului.
2. Pentru orice pereche $(A, B)$ de divizori ai lui $N$ care respectă $A > B$ şi pentru care $B$ îl divide pe $A$, se adaugă un arc orientat de la nodul asociat lui $A$ către nodul asociat lui $B$.
Observaţi că nu există o etichetare explicită a nodurilor, importantă fiind doar structura grafului.
Dându-se un graf orientat $G$, care se garantează că este DivisorGraph al unui număr natural, se cere cel mai mic număr care produce un DivisorGraph izomorf cu $G$. Deoarece acest număr poate fi foarte mare, se cere restul împărţirii sale la $10^9^ + 7$ (Un miliard şapte).
h2. Date de intrare
Fişierul de intrare $divisorgraph.in$ ...
Fişierul de intrare $divisorgraph.in$ va conţine pe prima linie un întreg $T$ care reprezintă numărul de teste din fişier. Fiecare test respectă următorul format: Prima linie conţine numerele $V$ şi $E$ reprezentând numărul de noduri, respectiv numărul de arce ale lui $G$. Următoarele $E$ linii conţin câte două numere $x$ şi $y$, semnificând că există arc $x -> y$.
h2. Date de ieşire
În fişierul de ieşire $divisorgraph.out$ ...
În fişierul de ieşire $divisorgraph.out$ se vor afla $T$ linii, fiecare conţinând răspunsul pentru testul corespunzător modulo $1000000007$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 3$
* $1 ≤ V ≤ 5.000$
* $0 ≤ E ≤ 450.000$
* Doua grafuri $A$ şi $B$ sunt izomorfe dacă şi numai dacă există o bijecţie între ele, $f$, astfel încât arcul $f(x) -> f(y)$ apare în B dacă şi numai dacă arcul $x -> y$ apare în $A$
* Există $2$ grupe de teste. Prima valoreaza $30$ de puncte şi respectă în plus restricţia $E ≤ 500$. Veţi avea feedback complet pe această grupă. Cea de a doua valorează $70$ de puncte şi respectă doar restricţiile precizate mai sus. Veţi avea feedback pe un test ales aleator din acestă grupă.
h2. Exemplu
table(example). |_. divisorgraph.in |_. divisorgraph.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
3 3
1 2
1 3
2 3
| 4
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="divisorgraph") ==
