$n$ اسمورف در درختی بزرگ و سرسبز زندگی می‌کنند. اسمورف‌ها با اعداد $0$ تا $n - 1$ شماره‌گذاری شده‌اند و هر کدام در خانه‌ای متمایز زندگی می‌کند. گارگامل، جادوگر خبیث، بارها و بارها اسمورف‌ها را اذیت کرده و به همراه هوگاتا و بالتازار سعی در تخریب درخت بزرگ آن‌ها کرده‌اند. درخت اسمورف‌ها به‌گونه‌ای است که خانه‌های اسمورف‌ها مانند رئوس و شاخه‌های درخت مانند یال‌های یک درخت(گراف ساده‌ی همبند و بدون دور) می‌باشد.

فقط «اسمورف‌های اعظم» می‌توانند با گارگامل مقابله کنند به طوری که اگر خانه‌ی اسمورفی به خانه‌ی هیچ یک از اسمورف‌های اعظم مسیر نداشته باشد، آن اسمورف به زودی از بین خواهد رفت. دقت کنید اسمورف‌های اعظم هیچ‌گاه از بین نمی‌روند.

گارگامل با دانستن این مسئله تصمیم گرفته است تا با شکستن برخی از شاخه‌های درخت، اسمورف‌ها را از بین ببرد. تماشای از بین رفتن اسمورف‌ها از دور، برای گارگامل جذاب‌ است. هوگاتا و بالتازار، شکستن شاخه‌ها را به صورت یک بازی انجام می‌دهند.

بازی به این‌ گونه است که هوگاتا و بالتازار به نوبت یکی از شاخه‌ها را می‌شکنند. سپس هر خانه‌ای که دیگر به اسمورف اعظمی نتواند برسد، خراب می‌شود و شاخه‌های متصل به آن از بین می‌روند. بازیکنی که در ابتدای نوبت او، شاخه‌ای باقی‌نمانده باشد، می‌بازد. بازی را بالتازار آغاز می‌کند.

گارگامل از شما خواسته است که برنامه‌ای بنویسید که برنده‌ی بازی را مشخص کند. البته پاپا اسمورف، یکی از اسمورف‌های اعظم، فامیل دوری هم دارد …!

در این سؤال شما باید تابع زیر را پیاده‌سازی کنید.

• string whoWins(int n, int *a, int *u, int *v)

این تابع $t$ بار صدا زده خواهد شد. آن را طوری پیاده‌سازی کنید تا در صورت برد بالتازار عبارت $``Baltazar''$ و در غیر این صورت عبارت $``Hogata''$ را برگرداند.

• $n$: تعداد خانه‌های درخت اسمورف‌ها
• $a$: یک آرایه به طول $n$. به ازای هر $i$ $(0 \le i \le n - 1)$ اسمورف شماره‌ی $i$ اسمورف اعظم است اگر و تنها اگر $a_i$ برابر یک باشد.
• $u, v$: دو آرایه به طول $n - 1$ که به ازای هر $i$ $(0 \le i \le n - 2)$ یک شاخه بین خانه‌ی اسمورف $u_i$ و اسمورف $v_i$ وجود دارد.

ارزیاب نمونه ورودی را به صورت زیر می‌خواند: در خط اول عدد $t$ داده می‌شود که تعداد موارد آزمون را نشان می‌دهد. سپس به ازای هر مورد آزمون، در خط اول عدد $n$ و در خط دوم $n$ عدد $a_0, a_1, \ldots, a_{n - 1}$ آمده است. سپس $n - 1$ خط آمده است که در خط $i$ ام به ترتیب دو عدد $u_i$ و $v_i$ نوشته شده است.

• زیرمسئله‌ی اول (۲۴ نمره): تنها یک اسمورف اعظم وجود دارد.
• زیرمسئله‌ی دوم (۷۶ نمره): بدون محدودیت اضافی.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \leq t \leq 5$
• $1 \leq n \leq 2 \times 10^5$
• $0 \le u_i, v_i \le n - 1$

• سوال بعد
• سوال قبل