Doprogramovanie do: 13. február 2023 23:59
11 dní
Popisy už neodovzdávajte. Ešte stále však môžete odosielať vaše programy, za ktoré dostanete časť bodov.
Počet bodov:
Popis:  12b
Program:  8b

Krtko sa chce dostať z tej masívnej KSP párty domov, ale keďže sa prejedol torty, tak sa len tak kotúľa. Snaží sa kráčať, no každým krokom sa bojí, že sa preváži a spadne. Preto, koľko krokov spraví pravou nohou, toľko ich musí spraviť aj ľavou, aby to nejak vybalansoval. Ale keďže je hrooozne najedený, tak sa nechce úplne nachodiť.

Úloha

Daný je graf s \(n\) vrcholmi, očíslovanými od \(1\) po \(n\), ktorého vrcholy reprezentujú Krtkove pozície na ceste domov po krokoch – čo vrchol, to krok (kam Krtko spraví krok, tam sa posunie celým telom; nemôže byť nohami v dvoch vrcholoch naraz). V grafe sú samozrejme aj nejaké iné možnosti krokov, kam nie nutne musí stúpiť. Hrana z \(a\) do \(b\) znamená, že z vrcholu \(a\) vie do \(b\) prejsť na jeden krok.

Nájdite cestu párnej dĺžky z vrcholu číslo \(1\) (miesto, kde bola párty) do vrcholu číslo \(n\) (miesto, kde Krtko býva), kratšiu ako \(2n\) (nechce sa predsa nachodiť). Krtko sa samozrejme ale vie stratiť a zamotať, a teda môže prejsť v grafe cez vrchol aj viackrát a po hranách tiež.

Formát vstupu

V prvom riadku vstupu sú čísla \(n\) (\(1 \leq n \leq 10^5\)) počet vrcholov, a \(m\) (\(1 \leq m \leq 10^6\)) počet hrán.

Nasleduje \(m\) riadkov popisujúcich hrany. V každom z nich sú dve čísla oddelené medzerou, čísla vrcholov medzi ktorými je hrana.

Pre sady vstupov platia nasledovné obmedzenia:

Sada 1 2 3 4
\(n \leq\) \(10\) \(100\) \(1\,000\) \(10^5\)
\(m \leq\) \(10\) \(1\,000\) \(10^4\) \(10^6\)

Formát výstupu

Na jeden riadok vypíšte zaradom čísla vrcholov cez ktoré Krtkova cesta prechádza – do ktorých Krtko spraví krok, oddelené medzerou (vrátane vrcholu \(1\) a \(n\)). Ak žiadna vyhovujúca postupnosť neexistuje vypíšte \(-1\).

Príklady

Input:

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

Output:

1 6 3 2 4 3 6

Input:

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

Output:

-1

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.