Bobby

Time limit: 0.2s Memory limit: 7MB Input: bobby.in Output: bobby.out

În timpul orei de geografie, amicul nostru Bobby primește o problemă năstrușnică de la colegul său, Fischer. Aflându-se într-o lipsă totală de idei și nevrând să-l dezamăgească pe Fischer, vă cere ajutorul. Năstrușnica problemă a lui Fischer este următoarea.

Cerință

Dându-se un șir de valori, reprezentând costurile a MM muchii bidirecționale, construiți un graf conex, având doar aceste muchii, astfel încât costul arborelui parțial de cost minim al său să fie maxim.

Date de intrare

Pe prima linie a fișierului de intrare bobby.in se găsesc două numere întregi, NN și MM, reprezentând numărul de noduri, respectiv numărul de muchii pe care trebuie să le aibă graful construit. Pe a doua linie se găsesc șase numere întregi, XX, YY, AA, BB, CC și DD, care vor genera șirul de MM valori, notat cu VV, după următoarele reguli:

  • V1=X\displaystyle V_1 = X;
  • V2=Y\displaystyle V_2 = Y;
  • Vi=(AVi2+BVi1+C) mod D\displaystyle V_i = (A \cdot V_{i-2} + B \cdot V_{i-1} + C)\text{ mod }D, oricare ar fi ii cu 3iM3 \leq i \leq M.

Date de ieșire

Pe prima linie a fișierului de ieșire bobby.out se va găsi un singur număr întreg, costul arborelui parțial de cost minim al grafului construit sau 1-1, în cazul în care nu se poate construi un graf care să respecte cerința.

Restricții și precizări

  • 2N,M1 000 0002 \leq N, M \leq 1 \ 000 \ 000;
  • 0X,Y,A,B,C,D1 000 000 0000 \leq X, Y, A, B, C, D \leq 1 \ 000 \ 000 \ 000, D0D \neq 0;
  • Între oricare două noduri din graful construit trebuie să existe cel mult o muchie.

Exemplu

bobby.in

4 5
1 1 1 1 1 3

bobby.out

1

Explicație

Șirul de MM muchii este: 1 1 0 2 01 \ 1 \ 0 \ 2 \ 0.
Construim graful astfel:

  • Între nodurile 11 și 22, muchie de cost 22.
  • Între nodurile 11 și 33, muchie de cost 00.
  • Între nodurile 11 și 44, muchie de cost 00.
  • Între nodurile 22 și 33, muchie de cost 11.
  • Între nodurile 33 și 44, muchie de cost 11.

Log in or sign up to be able to send submissions!