\documentclass{maratona} \begin{document} \begin{ProblemaAutor}{}{Pique Pega}{1}{256}{Arthur Andrade D'Olival} No grande Arraiá de São João, o aguardado Casamento Caipira virou uma tremenda confusão! O \textbf{Noivo} entrou em pânico na hora do "sim" e fugiu correndo. Imediatamente, o \textbf{Delegado} da festa foi acionado pelo pai da noiva para capturar o fujão e arrastá-lo direto para a barraca da Cadeia. O local da festa possui uma organização bem tradicional: o arraiá é composto por $n$ barracas numeradas de $1$ a $n$, que são conectadas por exatamente $n-1$ corredores de terra batida decorados com bandeirinhas coloridas. A organização foi feita de tal forma que existe sempre um único caminho simples caminhando pelos corredores entre quaisquer duas barracas. A perseguição começa com o Delegado na barraca $a$, e o Noivo escondido na barraca $b$. Eles correm em turnos alternados, e o \textbf{Delegado dá o primeiro pique de corrida}. \begin{itemize} \item No seu turno, o \textbf{Delegado} pode correr por até $d_a$ corredores de bandeirinhas para tentar encurralar o fujão. \item Na sua vez, o \textbf{Noivo} pode disparar por até $d_b$ corredores para tentar se afastar da autoridade. \end{itemize} A distância entre duas barracas é o número de corredores no único caminho entre elas. No desespero (ou para comer uma paçoca), ambos podem optar por não correr e permanecer na mesma barraca durante o seu turno. O movimento é focado apenas no destino: eles cruzam os corredores sem parar nas barracas intermediárias. O Delegado vence se, em até $10^{100}$ turnos, conseguir chegar na \textbf{mesma barraca} que o Noivo, efetuando a prisão. Caso contrário, se o Noivo conseguir sambar pelo arraiá e despistar o Delegado a noite inteira, o Noivo vence, e continua solteiro. Sua tarefa é determinar quem sairá vencedor dessa confusão junina, assumindo que tanto o Delegado quanto o Noivo corram e se escondam de maneira absolutamente ótima. Para cada caso de teste, imprima uma única linha contendo o vencedor dessa perseguição caipira: \texttt{Delegado} ou \texttt{Noivo}. \Entrada A primeira linha da entrada contém um inteiro $t$ ($1 \le t \le 10^4$), indicando o número de casos de teste. A primeira linha de cada caso de teste contém cinco inteiros: $n, a, b, d_a, d_b$ ($2 \le n \le 10^5$, $1 \le a, b \le n$, $a \neq b$, $1 \le d_a, d_b \le n-1$), representando o número de barracas no arraiá, a barraca inicial do Delegado, a barraca inicial do Noivo, o fôlego máximo de corrida do Delegado e o fôlego máximo de fuga do Noivo, respectivamente. As próximas $n-1$ linhas descrevem os corredores do arraiá. Cada linha contém dois inteiros $u$ e $v$ ($1 \le u, v \le n, u \neq v$), indicando um corredor direto de bandeirinhas ligando as barracas $u$ e $v$. É garantido que a soma de $n$ em todos os casos de teste não excede $10^5$. \Saida Para cada caso de teste, imprima uma única linha contendo o vencedor dessa perseguição caipira: \texttt{Delegado} ou \texttt{Noivo}. \ExemploEntrada \begin{Exemplo} \texttt{1} & \texttt{Delegado}\\ \texttt{4~3~2~1~2} & \\ \texttt{1~2} & \\ \texttt{1~3} & \\ \texttt{1~4} & \\ \rowcolor{gray!20}\texttt{1} & \texttt{Noivo}\\ \rowcolor{gray!20}\texttt{6~6~1~2~5} & \\ \rowcolor{gray!20}\texttt{1~2} & \\ \rowcolor{gray!20}\texttt{2~3} & \\ \rowcolor{gray!20}\texttt{3~4} & \\ \rowcolor{gray!20}\texttt{4~5} & \\ \rowcolor{gray!20}\texttt{5~6} & \\ \end{Exemplo} \Notas No primeiro caso de teste, o Delegado pode vencer se movendo para a barraca 1. Então, para onde quer que o Noivo se mova em seguida, o Delegado poderá se mover para a mesma barraca no turno seguinte. \begin{figure}[h] \centering \includegraphics[width=0.25\textwidth]{image1.png} \end{figure} No segundo caso de teste, o Noivo tem a seguinte estratégia para vencer. Para onde quer que o Delegado se mova, o Noivo sempre se moverá para aquela entre as barracas 1 ou 6 que estiver mais distante do Delegado. \begin{figure}[h] \centering \includegraphics[width=0.5\textwidth]{image2.png} \end{figure} Problema adaptado de \href{https://codeforces.com/contest/1405/problem/D}{Codeforces Round 668 (Div. 2, Problem D)}.\end{ProblemaAutor} \end{document}