| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 4 | 1 | 1 | 25.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$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 15 | $N ≤ 10$, $M ≤ 20$ |
| 2 | 20 | $N ≤ 1000$, $M ≤ 2000$ |
| 3 | 15 | 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.) |
| 4 | 50 | Nema dodatnih ograničenja. |
3 3 1 2 2 3 3 1
da
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
ne
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
da
Pojašnjenje trećeg probnog primjera: Riječ je o "jednoj trećini" grafa sa slike iznad, tj. o $2$-trostrukom grafu.