25127번 - Aromatična avantura 다국어

Gospodin Malnar uživa u šetnjama te ga stoga zanima šetnja kroz mirisne gradske vrtove. Gradske vrtove možemo zamisliti kao graf gdje su vrtovi označeni brojevima od $1$ do $n$. Između njih postoji točno $m$ neusmjerenih jedinstvenih bridova. Također znamo da vrt označen brojem $i$ ima koeficijent aromatičnosti $A_i$.

A svima je već poznato, da bi šetnja bila avanturistična, aromatičnost mora imati svoje uspone i padove tj. ako sa $v_1, v_2, \dots , v_k$ označimo vrtove posjećene $u$ šetnji (koji nisu nužno različiti), mora vrijediti $A_{v_1} < A_{v_2} > A_{v_3} < A_{v_4} \dots$

Sada Gospodina Malnara zanima do kojih sve vrtova može doći avanturističkom šetnjom krećući iz vrta $1$ (moguće je da šetnja Gospodina Malnara odmah i završi u tom vrtu).

U prvom su retku prirodni brojevi $n$ ($1 ≤ n ≤ 3 · 10^5$) i $m$ ($1 ≤ m ≤ 3 · 10^5$) iz teksta zadatka.

U sljedećem retku nalazi se $n$ brojeva od kojih je $i$-ti $A_i$ ($1 ≤ A_i ≤ 10^9$).

U $i$-tom od sljedećih $m$ redaka nalaze se po dva broja $u_i$ te $v_i$ ($1 ≤ u_i , v_i ≤ n$, $v_i \ne u_i$) koji označavaju da su vrtovi $u_i$ te $v_i$ spojeni bridom.

U prvom retku potrebno je ispisati broj $k$, broj vrtova do kojih Gospodin Malnar može doći.

U sljedećem retku potrebno je ispisati $k$ brojeva u rastućem poretku, oznake vrtova do kojih Gospodin Malnar može doći.