У некој далекој земљи има \(N\) метропола, који су међусобно повезане са \(M\) путева. Сваки пут спаја \(2\) метрополе и двосмеран је. Међутим, просторно планирање у овој држави је јако необично. Наиме, централна тема тамо су туре - низови метропола \(a_1,a_2,\cdots,a_n\) тако да су све те метрополе различите и да су \(a_1-a_2\), \(a_2-a_3\), \(\cdots\), \(a_n-a_1\) спојени путевима. Како је власт јако сујеверна, путеви су конструисани тако се свака тура састоји од тачно \(4\) метропола.

Ви као туриста у овој земљи желите да видите што више метропола. Стандардно би туриста обишао неку од тура, али како су све туре дужине \(4\) то делује малко досадно, па ви желите да изаберете ваш обилазак као најдужи низ различитих метропола тако да су сваке две узастопне спојене путем.

Описи функција

Потребно је да имплементирате функцију

• \(NajduziPut(N, M, U[\ldots], V[\ldots])\)

где је \(N\) број који представља број метропола, а \(M\) број који представља број путева. Низови \(U[\ldots]\) и \(V[\ldots]\) описују те путеве - \(i\)-ти пут спаја градове \(U[i]\) и \(V[i]\). Сви низови су индексирани од 1.

Функција треба да враћа број путева на најдужем могућем обиласку). ## Пример

Нека је \(N=4\), и нека је низ \(M=4\) и гране \(U=\{1,2,3,4\}\), \(V=\{2,3,4,1\}\): тада је најдужи обилазак \(1-2-3-4\), што има \(3\) пута, па је одговор \(3\) ## Ограничења

• \(1 \leq N,M \leq 200.000\)
• \(1 \leq U[i], V[i] \leq N\)
• \(U[i]\neq V[i]\)
• Могуће је од сваке метрополе стићи до сваке друге низом путева.

Подзадаци

Тест примери су подељени у \(6\) подзадатка:

• [11 поена]: \(N\le20\).
• [12 поена]: \(N\le2500\).
• [6 поена]: Не постоји ниједна тура.
• [21 поена]: Сваки пут се налази у највише једној тури.
• [22 поена]: Сваки пут који се налази у барем једној тури се налази у барем две туре.
• [28 поена]: Нема додатних ограничења.

Детаљи имплементације

Потребно је да пошаљете тачно један фајл metropole.cpp који имплементира поменуту функцију. Осим тражене функције, ваш фајл може садржати и додатне глобалне променљиве, помоћне функције и додатне библиотеке.

Ваша функција мора бити следећег облика:

int NajduziPut(int N, int M, int* U, int* V);

Вашим програмима је дозвољено да мењају садржај низова али не смеју да приступају ван граница датих низова.

Уз задатак, обезбеђен вам је “template” фајл code.cpp које можете користити и мењати по потреби. Такође вам је обезбеђен програм grader.cpp који служи да лакше тестирате кодове. Овај програм учитава са стандардног улаза следеће податке:

• У првом реду бројеве \(N\) и \(M\).
• У наредних \(M\) редова по један пар бројева: \(U[i]\) и \(V[i]\) .

Затим овај програм зове вашу функцију и штампа дужину пута коју ваша функција врати.