K-Star
Sa K-Star ćemo označiti stablo kod kojeg može da se uoči neki korenski čvor v, gde za svako njegovo podstablo T' važi da je stablo koje čine v i T' prost lanac dužine K.
InputPrvi red standardnog ulaza sadrži dva cela broja n (2 <= n <= 100 000) i K (1 <= K <= 10 000), gde n predstavlja broj čvorova u grafu. Potom se u svakom od narednih n - 1 redova učitavaju po dva cela broja a i b (a != b, 1 <= a, b <= n), koji označavaju da u grafu postoji grana {a, b}.
OutputPrvi red standardnog ulaza treba da sadrži 'Da', ako graf predstavlja K-Star, inače 'Ne'.
Ulaz:
Izlaz:
4 1
1 2
1 3
1 4Izlaz:
DaObjašnjenje:
Čvor 1 je povezan sa svakim od ostalih i svaka od tih grana čini jedan krak, odnosno traženi prosti lanci su:
1-2; 1-3; 1-4.
Ulaz:
Izlaz:
13 3
1 2
2 3
3 4
1 5
5 6
6 7
1 8
8 9
9 10
1 11
11 12
12 13
Izlaz:
DaObjašnjenje:
Traženi prosti lanci su:
1-2-3-4; 1-5-6-7; 1-8-9-10; 1-11-12-13.
Ulaz:
Izlaz:
6 2
1 2
2 3
1 4
1 5
1 6
Izlaz:
NeUlaz:
Izlaz:
5 1
1 2
1 3
2 3
5 4Izlaz:
NeObjašnjenje:
Graf nije stablo.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.