Domácí kolo

D: Kružítka a pravítka

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Zadání

Martin potřebuje na splnění domácího úkolu pravítko a kružítko. Protože ale nechce zbytečně utrácet, rozhodl se, že si pořídí jen jednu z pomůcek a druhou si půjčí od některého ze svých kamarádů.

Ostatním spolužákům se Martinův nápad zalíbil a chtějí problém s rýsovacími pomůckami vyřešit stejně. Každý ale má jiné kamarády a chce, aby některý z jeho kamarádů druhou pomůcku měl.

V Martinově třídě je N žáků. Dále víme, kteří spolužáci se spolu kamarádí (každé kamarádství je vzájemné). Každý žák si chce koupit právě jednu pomůcku (tedy nikdo si nekoupí pravítko i kružítko a zároveň nikdo nezůstane bez pomůcek a nebude si je obě půjčovat od kamarádů).

Určete, kteří spolužáci si mají koupit kružítka a kteří pravítka, aby si měl každý žák chybějící pomůcku od koho půjčit, nebo řekněte, že to není možné. Pokud existuje více možných řešení, vypište libovolné z nich.

Tvar vstupu

Na prvním řádku vstupního souboru je číslo T, počet problémů, které musíte vyřešit.

Pro každý problém dostanete na prvním řádku dvojici čísel N a M, tedy počet žáků a počet kamarádství mezi nimi.

Na každém z následujících M řádků jsou dvě čísla u a v splňující 1 \leq u < v \leq N, která znamenají, že žák číslo u se kamarádí se žákem číslo v. První žák má číslo 1.

Tvar výstupu

Pro každý problém vypište na první řádek ANO, pokud je možné podmínky ze zadání splnit, v opačném případě vypište NE.

Pokud řešení existuje, vypište na druhý řádek číslo P – počet žáků kteří si mají koupit pravítko – a na následujících P řádků čísla žáků, kteří mají pravítka koupit.

Lehká verze

  • 1 \leq T \leq 10
  • 1 \leq N \leq 10^6
  • 0 \leq M \leq 10^6
  • Každý žák má nejvýše dva kamarády.

Těžká verze

  • 1 \leq T \leq 10
  • 1 \leq N \leq 10^6
  • 0 \leq M \leq 10^6

Ukázkový vstup

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

Ukázkový výstup

ANO
2
1
3
ANO
3
1
3
5
NE

Vysvětlení ukázkového vstupu a výstupu

V prvním problému máme tři žáky, první se kamarádí se druhým a druhý se třetím. Kdyby si první a třetí žák koupili pravítko a druhý žák kružítko, mohou si první a třetí půjčit kružítko od druhého (oba jsou s ním kamarádi). Druhý žák si může pravítko půjčit od libovolného z kamarádů.

Ve druhém problému žáci situaci vyřeší, pokud si

  • žák č. 1 koupí pravítko a kružítko si půjčí od žáka č. 4
  • žák č. 2 koupí kružítko a pravítko si půjčí od žáka č. 1
  • žák č. 3 koupí pravítko a kružítko si půjčí od žáka č. 2
  • žák č. 4 koupí kružítko a pravítko si půjčí od žáka č. 3
  • žák č. 5 koupí pravítko a kružítko si půjčí od žáka č. 4

V posledním problému nemá třetí žák žádného kamaráda. Ať už si koupí pravítko nebo kružítko, nebude si mít druhou pomůcku od koho půjčit. Řešení tedy neexistuje.

První a třetí problém by se mohly vyskytnout v lehké variantě úlohy. Druhý problém nikoli, protože třeba hned první žák má tři kamarády.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)