Finále

F: Výběr průzkumníků

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

Nejsi finalista, takže se neobjevíš ve výsledcích.

Zadání (Řešení)

Jeden z nově postavených portálů vykazuje zvláštní vlastnosti, takže generál Kája pověřil kapitána Kubu vytvořením průzkumné jednotky z N = 3k průzkumníků. Kuba je ale omezen maximální přenosností portálu, která mu umožňuje vzít s sebou na misi jen třetinu (N/3) všech průzkumníků, které má k dispozici.

Jako správný velitel si je vědom toho, že by si všichni v této skupině měli navzájem věřit. Také ví, že existuje skupina průzkumníků o velikosti 2N/3, v níž si navzájem věří všichni. Kteří to jsou, ovšem netuší.

Aby celá mise skončila zdárně, je vaším úkolem najít libovolnou skupinu velikosti N/3, v níž si všichni navzájem věří.

Tvar vstupu

Na prvním řádku je číslo T – počet testů v jednom souboru. Na prvním řádku každého testu jsou dvě čísla NM – počet průzkumníků a dvojic, jež si věří. Na každém z následujících M řádků je dvojice čísel průzkumníků, kteří si navzájem věří. Průzkumníky číslujeme od 1 do N.

Tvar výstupu

Pro každý test vypište na samostatném řádku přesně N/3 čísel oddělených mezerou – čísla průzkumníků tvořících vhodnou skupinu v libovolném pořadí.

Lehká verze

  • T ≤ 10
  • N ≤ 27
  • M ≤ N(N – 1) / 2
  • Máte zaručeno, že N je dělitelné třemi.

Těžká verze

  • T ≤ 10
  • N ≤ 1000
  • M ≤ N(N – 1) / 2
  • Máte zaručeno, že N je dělitelné třemi.

Ukázkový vstup

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

Ukázkový výstup

1 5

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

Máme 6 průzkumníků, skupina čtyř z nich si musí navzájem věřit. Taková tu vskutku je, je tvořena průzkumníky 1, 3, 4, 5. Jako odpověď požadujeme libovolnou skupinu velikosti 2, tedy libovolnou dvojici průzkumníků, kteří si věří. Další správné odpovědi jsou tedy například 3 1, 4 5 nebo 2 3.

Jako odpověď nám postačuje libovolná skupina velikosti N/3, v níž si všichni věří. Proto je i odpověď 2 3 správná, přestože průzkumník číslo 2 nepatří do čtyřčlenné skupinky průzkumníků 1, 3, 4, 5.

Máš na to!

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