English statement

Jošicune treba da putuje po grafu. On je trenutno u čvoru ~1~, a cilj mu je da stigne do čvora ~N~. Postoji ~M~ grana koje spajaju neke čvorove. Jošicune u jednom potezu može da putuje kroz jednu granu i završi u čvoru sa druge strane te grane. Takođe, svakom čvoru je dodeljena neka boja. Jošicune bi hteo da što pre stigne do cilja, ali takođe ne želi da mu bude previše dosadno. Postane mu dosadno kada, na putu od ~1~ do ~N~, ~3~ puta za redom se nađe u čvoru iste boje, stoga ovo treba izbeći. Pomozite mu da pronađe najmanji broj poteza do cilja, pri čemu nikad ne poseti ~3~ čvora iste boje za redom.

Opis ulaza

Prva linija sadrži brojeve ~N, M~, koji predstavljaju broj čvorova i broj grana grafa (~2 \leq N,M \leq 10^5~).

Druga linija sadrži ~N~ različitih brojeva, koji predstavljaju boje čvorova (~1 \leq c_i \leq 10^9~, za svako ~1 \leq i \leq N~).

Narednih ~M~ linija sadrže po dva prirodna broja ~u_i, v_i~ koji predstavljaju da postoji grana između čvorova ~u_i~ i ~v_i~. Garantuje se nema duplih grana i petlji.

Opis izlaza

U prvoj i jedinoj liniji ispisati dužinu najkraćeg puta koji nije dosadan, ili ispisati ~-1~ ako takav ne postoji.

Primer ulaza

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

Primer izlaza

4

Objašnjenje primera

Ako ne bi imao uslova za boje, Jošicune bi mogao direktno da ode rutom ~1-2-4-5~ i stigao bi za ~3~ poteza. Međutim, kako su svi ovi iste boje, ova ruta otpada i nova najbolja ruta postaje ~1-2-3-4-5~.