Finále

D: Robotické vozíky

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

Máme dlouhou širokou ulici. Na obou stranách ulice jsou samé kanceláře a úřady. Každý úřad je rozdělen do dvou budov na protějších stranách ulice. Na jedné straně ulice jsou podatelny, kam lidé nosí vyplněné formuláře a různé jiné dokumenty, a na druhé straně sídlí úředníci, kteří je zpracovávají. Tam totiž mají větší klid, levnější nájem, lepší výhled z okna a vůbec je to tak lepší.

Jelikož jsme ve 21. století, ty dokumenty jsou papírové, takže je potřeba je přenášet mezi budovami. A protože jsme ve 21. století, tak tuto nudnou, opakovanou a jednoduchou práci zvládne i robot. Ulici proto křižují robotické vozíky. Jezdí po rovných barevných čárách namalovaných na ulici, jeden robot jezdí vždy z budovy číslo i na jedné straně do budovy qi na druhé straně. Budovy na obou stranách jsou očíslovány vzestupně od 0 do N − 1. Každá kancelář je spojena právě s jednou podatelnou.

Obvykle se stává, že podatelna není přímo naproti kanceláři. Mnoho čar se tedy kříží, ty pak nemohou mít stejnou barvu, jinak by robot mohl zabloudit. Když se ale dvě čáry nekříží, tak klidně můžou být stejné. Určete nejmenší počet barev, které v dané ulici můžeme použít.

Tvar vstupu

Na prvním řádku máte číslo T, počet vstupů. Každý vstup vypadá tak, že má na prvním řádku číslo N, a na druhém řádku N čísel q0 až qN − 1. To znamená, že i-tá budova na jedné straně je spojena s budovou qi na druhé straně.

Tvar výstupu

Na výstup vypište na samostatný řádek pro každý vstup jedno celé číslo, nejmenší počet barev, které se dají použít.

Lehká verze

  • T ≤ 10
  • N ≤ 1 000

Těžká verze

  • T≤ 20
  • N ≤ 200 000

Ukázkový vstup

1
6
2 0 5 1 4 3

Ukázkový výstup

3

Ulice se správně obarvenými čárami může vypadat například takto:

Máš na to!

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