Finále

C: Auta

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í)

Ve firmě Ricardo, která mimo jiné vyvíjí auta, mají zrovna na otestování N prototypů aut. A jak je v této firmě dobrým zvykem, na víkend si může každý zaměstnanec půjčit jedno auto domů a může si s ním jezdit, kde se mu zachce. Představ si, že jsi jeden z manažerů Ricarda a máš ta auta rozdělit. Od každého z tvých N − 1 podřízených jsi zjistil, která dvě auta by si přál půjčit. Jsi dobrý šéf, takže uděláš všechno proto, abys všem splnil jejich přání. A přitom jsi trochu zapomněl na sebe, ty přece chceš taky nějaké auto. Očísloval sis je od 1 do N podle toho, jak se ti zdá, že jsou dobrá, přičemž nejradši bys chtěl jedničku, tedy to nejlepší.

Je možné, že nemůžeš uspokojit všechny požadavky, to se pak samozřejmě nedá nic dělat, ale musíš to aspoň oznámit zaměstancům. Jinak musíš auta rozdělit tak, aby každý zaměstnanec měl jedno, a to právě jedno z dvojice, které si určil. Samozřejmě žádní dva zaměstnanci nesmí dostat stejné auto. Přitom musí jedno auto zbýt i na tebe. Jaké nejnižší číslo auta můžeš dostat?

Tvar vstupu

Na prvním řádku vstupního souboru máte číslo T, počet vstupů v souboru. Každý vstup vypadá tak, že má na prvním řádku N, počet aut, a dále N − 1 řádků, na každém dvě čísla od 1 do N, což je volba daného zaměstnance.

POZOR! Opravdu je tam nejdřív N, a pak N − 1 řádků patřících ke stejnému vstupu! Nemáš totiž zadaný požadavek sám od sebe.

Je možné, že více zaměstnanců bude chtít stejné auto, a také je možné, že nějaký zaměstnanec si přeje jedno konkrétní auto dvakrát. Pak jsou za něj na vstupu dvě stejná čísla.

Tvar výstupu

Pro každý vstup vypište na samostatný řádek nejmenší číslo auta, které můžete získat vy. Pokud neexistuje správné rozdělení, vypište −1.

Lehká verze

  • T ≤ 20
  • N ≤ 25

Těžká verze

  • T ≤ 30
  • N ≤ 100 000

Ukázkový vstup

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

Ukázkový výstup

1
-1
1

V prvním testu si můžeš zabavit první autíčko pro sebe, na prvního zaměstnance zbude auto číslo dvě, na druhého číslo tři a na třetího číslo čtyři.

V druhém testu nikdo nechce auto pět a šest, tedy čtyři zbylá auta nejde rozdělit mezi pět lidí.

Máš na to!

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