Fişierul intrare/ieşire:colors2.in, colors2.outSursăRMI 2018
AutorCostin OncescuAdăugată delaurageorgescuLaura Georgescu •laurageorgescu
Timp execuţie pe test2.25 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Colors2

Se consideră un graf conex neorientat cu N noduri şi M muchii. Iniţial, fiecare nod u are o culoare au, codificată printr-un număr natural între 1 şi N. Poţi modifica repetat culorile nodurilor prin operaţia au = min(au, av), unde u şi v sunt conectate de o muchie.

Dânduse o colorare finală b1 ... bN, determinaţi dacă se poate ajunge din a în b.

Date de intrare

Fişierul de intrare colors2.in se află mai multe teste care trebuie răspunse separat.
Pe prima linie se află numărul de teste. Fiecare test este structurat astfel:

N M
a1 a2 ... aN
b1 b2 ... bN
u1 v1
u2 v2
...

uM vM

Date de ieşire

În fişierul de ieşire colors2.out, pentru fiecare test trebuie printat, pe câte o linie separată, 1 dacă a poate fi transformată în b folosind operaţia menţionată şi 0 in caz contrar.

Restricţii

  • 1 ≤ N ≤ 150 000
  • N - 1 ≤ M ≤ 250 000
  • Pentru 15p, graful este o stea (M = N - 1 şi un nod este conectat la toate celelalte noduri), N2 ≤ 5 000 000
  • Pentru 7p, graful este complet, N ≤ 50, N * M ≤ 12 000 000
  • Pentru 8p, graful este un lant (M = N - 1), N2 ≤ 5 000 000
  • Pentru 15p, graful este un lant, fără altă restricţie
  • Pentru 7p, graful este un arbore, N2 ≤ 5 000 000
  • Pentru 16p, graful este un arbore, iar colorarea a este o permutare a mulţimii {1, 2, ..., N}
  • Pentru 10p, N * M ≤ 5 000 000

Exemplu

colors2.incolors2.out
2
4 4
3 3 2 1
2 1 2 1
1 2
2 3
3 4
4 2
4 4
3 3 2 1
1 2 2 1
1 2
2 3
3 4
4 2
1
0

Explicaţii

Pentru primul graf, operaţiile necesare sunt:
a2 = min(a2, a3) = 2
a1 = min(a1, a2) = 2
a2 = min(a2, a4) = 1

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?