시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB41125.000%

문제

Za nenegativni cijeli broj $k$, definiramo pojam $k$-trostrukog grafa rekurzivno na sljedeći način.

Za graf kažemo da je $0$-trostruki ako se sastoji od točno jednog čvora.

Za $k ≥ 1$, kažemo da je graf $k$-trostruki ako je nastao uzimanjem neka tri $(k - 1)$-trostruka grafa $G$, $H$ i $I$, odabirom po jednog čvora iz svakog od ta tri grafa te dodavanjem tri nova brida koja spajaju odabrane čvorove.

Slika ispod prikazuje jedan $3$-trostruki graf.

Vaš je zadatak za zadani ulazni graf odrediti je li on $k$-trostruki za neki $k$.

입력

U prvom su retku dva prirodna broja $N$ i $M$, redom broj čvorova i broj bridova u grafu.

U svakom od sljedećih $M$ redaka su dva prirodna broja $a$ i $b$ ($1 ≤ a, b ≤ N$), koja predstavljaju brid između čvorova $a$ i $b$. Nijedan brid ne povezuje čvor sa samim sobom te nijedan brid neće biti naveden dvaput.

출력

U jedinom retku ispišite da ukoliko je zadani graf $k$-trostruki za neki $k$, odnosno ne ako nije.

서브태스크

U svim podzadacima vrijedi $1 ≤ N ≤ 200\,000$ i $1 ≤ M ≤ 300\,000$.

번호배점제한
115

$N ≤ 10$, $M ≤ 20$

220

$N ≤ 1000$, $M ≤ 2000$

315

Ako je graf $k$-trostruki, garantirano je da je nastao tako da su u svakom koraku odabrana upravo tri čvora tako da je svaki bio odabran u prethodnom koraku u pripadajućem grafu nižeg stupnja trostrukosti. (Uvijek se bira "srednji" čvor.)

450

Nema dodatnih ograničenja.

예제 입력 1

3 3
1 2
2 3
3 1

예제 출력 1

da

예제 입력 2

9 12
1 2
2 3
3 1
3 4
4 5
3 5
5 6
6 7
7 5
7 8
9 8
7 9

예제 출력 2

ne

예제 입력 3

9 12
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7
1 7
7 4
4 1

예제 출력 3

da

힌트

Pojašnjenje trećeg probnog primjera: Riječ je o "jednoj trećini" grafa sa slike iznad, tj. o $2$-trostrukom grafu.

채점 및 기타 정보

  • 예제는 채점하지 않는다.