CSES - Toimistot
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Bittimaassa on n kaupunkia, joiden välillä on n-1 tietä. Minkä tahansa kahden kaupungin välillä on olemassa reitti.

Haluat perustaa joihinkin kaupunkeihin toimiston, mutta rajoituksena on, että jokaisen kahden toimiston etäisyys tulee olla vähintään d.

Mikä on suurin määrä toimistoja, jotka voit perustaa?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja d: kaupunkien määrä ja pienin sallittu etäisyys. Kaupungit on numeroitu 1,2,\dots,n.

Sitten syötteessä on n-1 riviä, jotka kuvaavat tiet. Jokaisella rivillä on kaksi kokonaislukua a ja b: kaupunkien a ja b välillä on tie.

Tuloste

Tulosta ensin yksi kokonaisluku: suurin toimistojen määrä k.

Tulosta sitten k lukua: kaupungit, joihin toimistot perustetaan. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Rajat

  • 1 \le n,d \le 2 \cdot 10^5
  • 1 \le a,b \le n

Esimerkki

Syöte:

5 3
1 2
2 3
3 4
3 5

Tuloste:

2
1 4

Selitys: Voit perustaa korkeintaan kaksi toimistoa. Yksi ratkaisu on perustaa toimistot kaupunkeihin 1 ja 4.