7. Jedenie v polceste

Kašľať na programovanie, AIčky a počítače. Treba sa vrátiť ku koreňom, dotknúť sa trávy. Preto ste zanevreli na Korešpondenčný Seminár z Programovania a otvorili ste si radšej agentúru Komfortné Spojenie s Prírodou, ktorá ponúka caterované túry s horským vodcom. Vymysleli ste si ponuku \(n\) túr a na každej by ste chceli ponúkať turistom teplý obed.

Nosiť jedlo zo sebou zaberá priveľa miesta (a ešte by vychladlo), preto ste sa radšej rozhodli otvoriť poľné kuchyne na miestach, kde sa nachádza prestávka na obed. Okrem toho, že zo sebou nemusíte nosiť jedlo, majú poľné kuchyne tú výhodu, že vedia ponúkať obed pre viac než jednu túru.

Keďže treba maximalizovať zisk, chceli by ste postaviť čo najmenej poľných kuchýň. Ale keďže sľubujete zákazníkom Komfort, obed by mal byť na správnom mieste – a to čo najbližšie k polceste túry. Avšak, vaše biznis plány začali byť príliš ambiciózne, a možno sa budete na ten počítač obrátiť ešte raz, aby ste tento logistický problém vyriešili.

Úloha

Existuje \(n\) zaujímavých miest, po ktorých môžete viesť turistov. Medzi \(n-1\) pármi z nich vedú turistické chodníky, pričom sa dá z každého miesta dostať na každé iné nejakou postupnosťou ciest (čiže hory majú tvar stromu).

Agentúra Komfortné Spojenie s Prírodou ide ponúkať \(m\) túr. Trasa každej túry je najkratšia cesta medzi dvoma zaujímavými miestami (dá sa ukázať, že pre každú dvojicu miest existuje presne jedna najkratšia cesta). Obed by mal byť ponúkaný presne v polceste túry, pričom dĺžka cesty je počet zaujímavých miest na nej. Poľnú kuchyňu nechceme otvárať v strede turistického chodíka, a preto v prípade, že na túry navštívime párny počet zaujímavých miest, \(a_1,\dots,a_{2k}\), obed môže byť na ktoromkoľvek z dvoch miest najbližšie ku polceste, čiže buď v \(a_k\) alebo \(a_{k+1}\).

Koľko najmenej kuchýň musíte otvoriť?

Formát vstupu

V prvom riadku vstupu sú dva čísla \(n\) a \(m\) (\(1 \leq n, m \leq 10^5\)) – počet zaujímavých miest a počet ponúkaných túr, oddelené medzerou.

Na ďalších \(n-1\) riadkoch nasleduje popis turistických chodníkov. Popis každého chodníka pozostáva z dvoch čísel \(a\) a \(b\) (\(1\leq a,b\leq n\)) oddelených medzerou, označujúcich, že medzi miestami \(a\) a \(b\) existuje priamy turistický chodník.

Je garantované, že sa dá nejakou postupnosťou turistických chodníkov presunúť medzi každou dvojicou zaujímavých miest.

Na ďalších \(m\) riadkoch nasleduje popis túr: popis každej túry pozostáva z dvoch čísel \(a\) a \(b\) (\(1\leq a,b,\leq n\)) oddelených medzeru, označujúcich, že Komfortné Spojenie s Prírodou ponúka túru, ktorá začína na mieste \(a\) a končí na mieste \(b\).

Formát výstupu

Na prvom riadku vstupu vypíšte jedno celé číslo \(k\) – najmenší počet kuchýň ktoré musíte otvoriť.

Na druhom riadky vstupu vypíšte \(k\) medzerou oddelených čísel – miesta na ktorých by ste mali otvoriť poľné kuchyne, tak aby pokryli potreby všetkých ponúkaných túr. Ak existuje viacero riešení, môžete vypísať ľubovoľné z nich.

Hodnotenie

Úloha má osem testovacích sád. V jednotlivých sadách platia nasledujúce obmedzenia:

V sadách \(4\) a \(5\) navyše platí, že každá túra obsahuje presne nepárny počet miest.

V sadách \(2\) a \(6\) navyše platí, že \(i\)-ty turistický chodník spája miesta číslo \(i\) a \(i+1\), čiže chodníky tvoria jednu dlhú cestu.

Príklady

Input:

5 3
1 2
2 3
3 4
4 5
1 5
3 3
1 4

Output:

1
3

Tento príklad by sa mohol nachádzať v druhej alebo šiestej sade. Prvá aj druhá túra musia mať obe obed na treťom mieste. Tretia túra môže mať obed buď na druhom, alebo na treťom mieste. Ak si vyberieme tretie, stačí nám na pokrytie všetkých túr len jedna poľná kuchyňa. Všimnite si, že druhá túra začína aj končí tom istom mieste – na tom mieste teda musí byť aj obed.

Input:

7 4
1 2
1 3
5 2
3 4
2 6
7 5
2 4
6 3
7 2
7 7

Output:

3
1 7 5

Prvá túra potrebuje poľnú kuchyňu buď v prvom alebo treťom mieste. Pre druhú túru potrebujeme otvoriť poľnú kuchyňu v druhom, alebo prvom mieste. Zabezpečiť catering pre tieto dve túry teda vieme tak, že otvoríme kuchyňu v prvom mieste. Hoci sa tretia túra čiastnočne prekrýva s prvou, a štvrtá s treťou, pri týchto túrach nemáme na výber: poľné kuchyne musíme postaviť v piatom a siedmom mieste.