تا به حال اسم بازی «گراف حنایی» رو شنیدید؟
این بازی که حدود $20$ سالی است مد شده است، روی یک گراف وزن‌دار بدون جهت انجام می‌شود. دو نفر که هر کدام یک راس را به عنوان پایگاه دارند، به صورت نوبتی روی این گراف بازی می‌کنند. گراف این بازی، یک گراف وزن‌دار و بدون‌جهت است که ممکن است یال چندگانه هم داشته باشد. وزن یالهای گراف همواره اعداد صحیح نامنفی هستند. در این بازی، هر راس گراف یک امتیاز دارد. امتیاز هر راس یک عدد صحیح است که ممکن است مثبت یا منفی باشد. بازی به این صورت پیش می‌رود که هرکس در نوبت خود یک عدد صحیح نامنفی مثلا $x$ را اعلام می‌کند؛ سپس امتیاز تمام رئوسی که فاصله‌شان تا پایگاه آن بازیکن کمتر یا مساوی $x$ است به آن بازیکن می‌رسد و امتیاز این رئوس صفر می‌شود. قانون اساسی بازی این است که هر دفعه یک بازیکن در نوبت خود باید امتیاز حداقل یک راس جدید که تا به حال امتیازش به کسی نرسیده را کسب کند. نهایتا وقتی امتیاز تمام رئوس کسب شد بازی پایان می‌پذیرد و برنده کسی است که امتیاز بیشتری کسب کرده باشد.
فصل مسابقات «گراف حنایی» رسیده است. در مسابقات «گراف حنایی» $k$ مسابقه به صورت همزمان برگزار می‌شود. اول مسابقه هر بازیکن یک راس را به عنوان پایگاه انتخاب می‌کند و بازی را شروع می‌کند. خیکوله که خیلی به این بازی و مسابقات آن علاقه‌مند شده می‌خواهد قبل انجام بازی بداند اگر دو بازیکن بهترین بازی خود را انجام دهند آنگاه چه کسی برنده بازی خواهد بود. نفر اول، یا نفر دوم.
برنامه‌ای بنویسید که ابتدا $k$ و سپس $k$ گراف وزن‌دار و بدون‌جهت را به همراه امتیازات رئوس گراف و دو راسی که پایگاه نفر اول و نفر دوم است را از ورودی بخواند و $k$ عدد که مشخص می‌کند در هر بازی استراتژی برد با کدام بازیکن است را در خروجی چاپ کند.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 2 4 4 1 4 2 3 4 2 3 1 5 3 2 1 3 2 5 -11 1 2 5 4 1 2 4 2 3 5 2 4 2 4 5 2 2 2 -5 -4 6 1 2 | 2 1 |