% !TeX program=lualatex

\documentclass[12pt]{article}
\input{structure.tex}
\renewcommand{\bottomtitlespace}{2cm}

\begin{document}
	

\problem{Задача CT1. Дърво}
\renewcommand{\header}{
	ТРЕНИРОВКА\\
	Група C – 7, 8 клас
}

Зорани имал дърво от $N$ върха и $N - 1$ ребра и от скука решил да сложи числа на върховете. Той слага стойност от $1$ до $N$ на всеки връх, като всяка стойност се среща точно по веднъж.
След много опити той осъзнал, че най-важно за него за едно дърво било да има колкото се може по-малко ребра, които свързват върхове, чийто най-голям общ делител е по-голям от $1$.

По-формално нека означим с $v_i$ стойността на връх $i$, то Зорани иска да минимизира бройката ребра $(a,b)$, за които $\gcd(v_a,v_b) > 1$.

\textbf{Задачата е output-only. Предоставени са ви 10 теста. Трябва локално да генерирате своите отговори за всеки един тест.}




\subsection{Вход}

Всеки тест се състои от няколко подтеста.
На първия ред на файла е въведен броя подтестове. Всеки първи ред от един подтест съдържа числото $N$.
На следващите $N - 1$ реда се въвеждат по $2$ числа -- $a$ и $b$, това означава, че има ребро между връх $a$ и връх $b$.
Всички подтестове са с еднакъв брой върхове.

\subsection{Изход}

За всеки подтест отпечатайте на отделен ред стойностите $v_1,v_2....,v_N$.


\subsection{Оценяване}

Нека с $M$ означим общия брой ребра от всички подтестове, а с $X$ означим общия брой ребра, за които $gcd(v_a,v_b) > 1$ от всички подтестове, а освен това $R = \frac{X}{M}$. Резултатът ви за всеки тест се изчислява по следния начин:
\begin{itemize}
	\item ако $R > 0.4$ ще получите $0$ т.
	\item ако $0.33 < R \leq 0.4$ ще получите $1$ т.
	\item ако $0.26 < R \leq 0.33$ ще получите $2$ т.
	\item ако $0.19 < R \leq 0.26$ ще получите $3$ т.
	\item ако $0.12 < R \leq 0.19$ ще получите $4$ т.
	\item ако $0.05 < R \leq 0.12$ ще получите $5$ т.
	\item ако $0.01 < R \leq 0.05$ ще получите $6$ т.
	\item ако $0.005 < R \leq 0.01$ ще получите $7$ т.
	\item ако $0.001 < R \leq 0.005$ ще получите $8$ т.
	\item ако $0.0 < R \leq 0.001$ ще получите $9$ т.
	\item ако $R = 0$ ще получите $10$ т.
\end{itemize}

\subsection{Качване на изходните файлове}

Името на изходния файл за тест с номер \texttt{xx} трябва да бъде

\[
\texttt{tree.xx.out}
\]

За тестове от $1$ до $9$ номерът се записва с водеща нула. Например изходът за осмия тест трябва да бъде във файл \texttt{tree.08.out}, а изходът за десетия -- във файл \texttt{tree.10.out}.

На системата се качва \texttt{ZIP} архив, който съдържа поне един изходен файл. Изходните файлове трябва да се намират директно в архива, а не в поддиректория. Файлове с други имена се игнорират. Ако в архива липсва файл за даден тест, това качване не променя резултата Ви за този тест.

Всяко качване на архив се счита за един събмит, независимо колко изходни файла съдържа архивът. Ако качите изходи за един и същи тест в повече от един събмит, за крайното класиране се взема най-добрият резултат, постигнат от Вас на този тест. Невалиден изход носи $0$ точки за съответния тест, но не оказва влияние, ако имате по-добри резултати за същия тест от предишен събмит.

\end{document}
