Domácí kolo

E: Směrovníky

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

Soutež skončila. Získané body již nejdou do výsledků.

Zadání (Řešení)

Je den před finále Kasiopey a organizátoři si uvědomili, že ještě nemají vymyšlené všechny úlohy. Jediné, co jim zbývá, je prodloužit soutěžícím cestu na finále, aby stihli dokončit zadání. V každém městě je směrovník ukazující směrem k místu konání finále a máte za úkol otočit nejvýše jeden směrovník tak, aby součet délek cest do finále pro všechny soutěžící byl co největší. Ale pozor, chceme, aby se všichni opravdu na finále dostali!

Existuje N měst očíslovaných od 0 až po N-1. Ve městě 0 se koná finále. Pro každé město kromě 0 je zadaný počet účastníků, kteří v něm bydlí. Některá města sousedí cestou a všechny cesty mezi sousedícími městy jsou dlouhé 1 km. V každém městě je směrovník na finále, který ukazuje na nějaké vedlejší (t.j. cestou se dotýkající) město. Soutěžící se vždy podívá na směrovník ve městě, ve kterém právě je, a vydá se po cestě, na kterou ukazuje. Skončí, až když dorazí do města 0, ve kterém se koná finále. Délka celé jeho trasy je součet délek cest, po kterých přešel, tedy počet cest, neboť všechny jsou stejně dlouhé. Vaší úlohou je otočiť nejvýše jeden směrovník na jinou existující cestu tak, aby se každý soutěžící jednou dostal do finálního města 0 a zároveň aby součet délek jejich tras byl nejvyšší možný.

Směrovníky zadané na vstupu určitě každého účastníka dovedou bezpečně do cíle, nemusí ovšem vést po nejkratší možné cestě.

Tvar vstupu

Na prvním řádku je číslo T označující počet vstupů, které máte vyřešit. Každý vstup má následující tvar:

Na prvním řádku jsou čísla N a M označující počet měst a počet cest mezi městy.
Na každém z dalších M řádků je mezerou oddělená dvojice čísel U, V pro která platí 0 <e; U, V < N. Ta značí, že mezi městy U a V vede cesta.
Na každém z dalších N-1 řádků je popis města, uspořádané jsou vzestupně, nejprve popis města 1, potom 2 až do N-1. Popis města i se skládá z mezerou oddělených čísel Ui a Si. Ui je značí počet účastníků začínajících ve městě i. Si je číslo města, které sousedí s i, a ukazuje na něj směrovník města i.

Tvar výstupu

Pokud je optimální neotočit žádný směrovník, vypište na výstup jediné číslo 0.

Jinak vypište dvojici čísel A B oddělených mezerou. A je číslo města, ve kterém otáčíte směrovník, a B je sousední město, do kterého bude směrovník po vaší změně ukazovat. Pokud existuje více optimálních řešení, vypište libovolné z nich.

Lehká verze

  • T = 10
  • N ≤ 1 000
  • M ≤ 700 000
  • Ui ≤ 1 000 000

Těžká verze

  • T = 10
  • N ≤ 100 000
  • M ≤ 700 000
  • Ui ≤ 1 000 000

Ukázkový vstup

4
3 3
0 1
0 2
1 2
2 0
1 0
3 2
0 1
0 2
2 0
1 0
3 3
0 1
0 2
1 2
2 0
1 1
3 3
0 1
0 2
1 2
2 2
1 0

Ukázkový výstup

1 2
0
0
0

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

V prvním vstupu máme tři města, mezi kterými vedou všechny cesty. Z města 1 i z města 2 vede směrovník přímo do cíle. Jelikož jsou v městě 1 dva lidé a v městě 2 jeden človek, tak se nám vyplatí otočit směrovník v městě 1 na město 2. Tím zvýšíme součet délek cest ze 3 na 5. Kdybychom otočili směrovník v městě 2, tak bychom součet zvýšili jen na 4.

V druhém případě nám chybí cesta mezi městy 1 a 2, takže nemáme žádnou možnost, jak směrovník otočit.

V třetím případě směrovníky otočit můžeme, ale už na vstupu je optimální řešení, takže není co vylepšit.

V posledním případě síce na vstupu není optimální řešení, ale bylo by nutné otočit dva směrovníky, abychom se k němu dostali. Jedním otočením řešení jen zhoršíme, proto raději neotáčíme nic.

Máš na to!

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