Fişierul intrare/ieşire:drumuri3.in, drumuri3.outSursăAlgoritmiada 2011, Runda 2
AutorDaniel PasailaAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.4 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Drumuri3

Bercea tocmai şi-a procurat (prin mijloace îndoielnice) Q limuzine. Acum, pentru a arăta tuturor noile sale achiziţii, el s-a hotărât să facă mai multe plimbări prin oraş, oraşul fiind de fapt un graf neorientat cu N noduri şi M muchii. Un drum se defineşte ca fiind o secvenţă de noduri a1, a2, ..., ak astfel încât să existe muchia (ai, ai+1), oricare ar fi 1ik-1. Astfel orice nod poate fi folosit de oricâte ori într-un drum, la fel şi orice muchie. Lungimea unui drum este numărul de noduri care fac parte din drumul respectiv.
Totuşi Bercea nu doreşte să facă drumuri mai lungi de K noduri, deoarece atunci ar putea ieşi din sfera sa de influenţă din oraş. Aşadar, fiind date Q perechi de noduri i si ji, aflaţi numărul de drumuri care încep în nodul i, se termină in nodul ji, iar lungimea fiecărui drum este ≤ K.
Deoarece numărul de drumuri poate fi foarte mare şi Bercea nu ştie să numere decât până la câte milioane de € are, afişaţi răspunsul modulo 10 007.

Date de intrare

Fişierul de intrare drumuri3.in va conţine pe prima linie numerele naturale N, M, K şi Q cu semnificaţia de mai sus. Următoarele M linii vor conţine câte două numere naturale reprezentând două noduri între care există o muchie. Următoarele Q linii vor conţine câte două numere naturale i şi ji reprezentând perechile de oraşe între care Bercea doreşte să se plimbe.

Date de ieşire

În fişierul de ieşire drumuri3.out se vor afişa Q linii cu numerele dorite modulo 10 007.

Restricţii şi precizări

  • 1 ≤ N ≤ 100
  • 1 ≤ K ≤ 5 000
  • 1 ≤ Q ≤ 2 500
  • Graful este conex (există cel puţin un drum între oricare două perechi de noduri).
  • O muchie nu va apărea în fişierul de intrare de mai multe ori.
  • Nu va exista în fişierul de intrare o muchie de la un nod la el însuşi.
  • iji

Exemplu

drumuri3.indrumuri3.out
6 15 4 2
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
1 2
1 6
26
26
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content