Jesienna wycieczka

30.10.2010
TrudnośćTrudnośćTrudność

Jesienna wycieczka

Limit czasowy: 1000 milisekund
Limit pamięciowy: 128000 kilobajtów


W związku z piękną jesienią za oknami Jakub i Alicja postanowili wybrać się na wycieczkę. W tym celu planują pojechać samochodem do pewnej malowniczej wsi, następnie trochę pochodzić po okolicy i wrócić do miejsca w którym zaparkowali samochód. Jakub nie chce rozczarować Alicji więc trasa wycieczki musi być ciekawa. Trasa wycieczki jest ciekawa, gdy nie prowadzi przez tą samą ścieżkę lub wieś wielokrotnie (z wyjątkiem miejsca początkowego). Ponieważ Jakub jest przesądny, trasa wycieczki musi przechodzić przez parzystą liczbę wsi. Pomóż Kubie sprawdzić czy da się znaleźć ciekawą wycieczkę w zadanej okolicy.
 

Wejście

Pierwsza linia zawiera dwie liczby całkowite n (1<=n<=100000) i m (1<=m<=200000) oznaczające kolejno ilość wsi oraz ilość ścieżek w okolicy.
Kolejne m lini zawiera kolejne ścieżki łączące wsie. Opis pojedynczej ścieżki składa się z 2 różnych liczb całkowitych u i v (0<=u,v<n) oznaczające, że tą ścieżką da się dojść zarówno ze wsi o numerze u do wsi o numerze v, jak również ze wsi o numerze v do wsi o numerze u. Pary na wejściu nie powtarzają się.

Wyjście:

Jeśli nie istnieje żadna ciekawa wycieczka to wypisz "BRAK". W przeciwnym wypadku wypisz "JEST".

 

Przykład

Dla danych wejściowych:
4 4
0 1
1 2
2 3
0 3

poprawną odpowiedzią jest:
JEST

Dla danych wejściowych:
3 3
0 1
1 2
0 2

poprawną odpowiedzią jest:
BRAK

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
5
Twoja ocena: Brak Ocena: 5 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com