Fişierul intrare/ieşire:divisorgraph.in, divisorgraph.outSursăAlgoritmiada 2014, Runda Finala
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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ă 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.

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 109 + 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. Următoarele E linii conţin câte două numere x şi y, semnificând că există arc x -> y.

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

Exemplu

divisorgraph.indivisorgraph.out
1
3 3
1 2
1 3
2 3
4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content