Fişierul intrare/ieşire:	divisorgraph.in, divisorgraph.out	Sursă	Algoritmiada 2014, Runda Finala
Autor	Mihai Calancea	Adăugată de	Mihai Calancea •klamathix
Timp execuţie pe test	0.5 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Divisorgraph

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 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.

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⁹ + 7 (Un miliard şapte).

Date de intrare

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.

Date de ieşire

Î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.

Restricţii

• 1 ≤ V ≤ 5.000
• 1 ≤ E ≤ 500.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

Exemplu

Cum se trimit solutii?