CSES - Väritys
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Puussa on nn solmua, joista jokaisella on tietty väri väliltä 1m1 \ldots m.

Tehtäväsi on laskea, mikä on suurin mahdollinen etäisyys kahden samanvärisen solmun välillä.

Syöte

Syötteessä on ensin kaksi kokonaislukua nn ja mm: puun solmujen määrä ja värien määrä. Solmut on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n, ja värit on numeroitu kokonaisluvuin 1,2,,m1,2,\ldots,m.

Sitten syötteessä on nn lukua c1,c2,,cnc_1,c_2,\ldots,c_n, jotka kuvaavat kunkin solmun värin.

Lopuksi syötteessä on n1n-1 riviä, jotka kuvaavat puun rakenteen. Jokaisella rivillä on kaksi kokonaislukua aa ja bb: solmujen aa ja bb välillä on kaari.

Voit olettaa, että puussa on kaksi solmua, jotka ovat samanvärisiä.

Tuloste

Tulosta suurin etäisyys kahden samanvärisen solmun välillä.

Rajat

  • 2n1052 \le n \le 10^5
  • 1m1051 \le m \le 10^5
  • 1cim1 \le c_i \le m
  • 1a,bn1 \le a,b \le n

Esimerkki

Syöte:

4 3
3 1 2 3
1 2
2 3
2 4

Tuloste:

2