تا به حال اسم بازی «گراف حنایی‎» رو شنیدید؟

این بازی که حدود ‎$20$‎ سالی است مد شده است، روی یک گراف وزن‌دار بدون جهت انجام می‌شود. دو نفر که هر کدام یک راس را به عنوان پایگاه دارند، به صورت نوبتی روی این گراف بازی می‌کنند. گراف این بازی، یک گراف وزن‌دار و بدون‌جهت است که ممکن است یال چندگانه هم داشته باشد. وزن یال‌های گراف همواره اعداد صحیح نامنفی هستند. در این بازی، هر راس گراف یک امتیاز دارد. امتیاز هر راس یک عدد صحیح است که ممکن است مثبت یا منفی باشد. بازی به این صورت پیش می‌رود که هرکس در نوبت خود یک عدد صحیح نامنفی مثلا ‎$x$‎ را اعلام می‌کند؛ سپس امتیاز تمام رئوسی که فاصله‌شان تا پایگاه آن بازیکن کمتر یا مساوی ‎$x$‎ است به آن بازیکن می‌رسد و امتیاز این رئوس صفر می‌شود. قانون اساسی بازی این است که هر دفعه یک بازیکن در نوبت خود باید امتیاز حداقل یک راس جدید که تا به حال امتیازش به کسی نرسیده را کسب کند. نهایتا وقتی امتیاز تمام رئوس کسب شد بازی پایان می‌پذیرد و برنده کسی است که امتیاز بیشتری کسب کرده باشد. ‎

• تبصره ‎۱‎: همواره پایگاه دو بازیکن دو راس متفاوت در نظر گرفته می‌شود.‎
• تبصره ‎۲‎: امتیاز راسی که پایگاه بازیکن روی آن است هم مثل بقیه‌ی رئوس باید کسب شود. یک بازیکن می‌تواند با اعلام عدد صفر؛ امتیاز راسی که پایگاه روی آن است به علاوه‌ی بقیه‌ی رئوسی که فاصله‌شان تا پایگاه صفر است را کسب کند.

فصل مسابقات «گراف حنایی»‎ رسیده است. در مسابقات «گراف حنایی» $k$‎ مسابقه به صورت همزمان برگزار می‌شود. اول مسابقه هر بازیکن یک راس را به عنوان پایگاه انتخاب می‌کند و بازی را شروع می‌کند‌. خیکوله که خیلی به این بازی و مسابقات آن علاقه‌مند شده می‌خواهد قبل انجام بازی بداند اگر دو بازیکن بهترین بازی خود را انجام دهند آنگاه چه کسی برنده بازی خواهد بود. نفر اول، یا نفر دوم.

برنامه‌ای بنویسید که ابتدا ‎$k$‎ و سپس ‎$k$‎ گراف وزن‌دار و بدون‌جهت را به همراه امتیازات رئوس گراف و دو راسی که پایگاه نفر اول و نفر دوم است را از ورودی بخواند و ‎$k$‎ عدد که مشخص می‌کند در هر بازی استراتژی برد با کدام بازیکن است را در خروجی چاپ کند.

• در خط اول ورودی عدد ‎$(1 \leq k \leq 5)$‎ آمده است که نشان دهنده‌ی تعداد بازی‌های همزمان در مسابقات است‎.
• سپس ‎$k$‎ بلوک می‌آید که هر بلوک نشان‌دهنده‌ی وضعیت کامل یک بازی است.
• در خط اول بلوک ‎$(2 \leq n \leq 2000)$‎ و ‎$(n-1 \leq e \leq 100000)$‎ تعداد رئوس و تعداد یالهای گراف آمده است.
• سپس در ‎$e$‎ خط بعدی، در هر خط سه عدد ‎$(1 \leq v \leq n)$ $(1 \leq u \leq n)$ $(0 \leq w \leq 10^6)$ (اول ‎$v$‎ سپس ‎$u$‎ و بعد ‎$w$)‎ آمده است که نشان دهنده‌ی این است که رئوس ‎$v$‎ و ‎$u$‎ با یک یال به وزن ‎$w$‎ به هم متصلند.
• در خط بعدی ‎$n$‎ عدد آمده است که عدد ‎$i$‎ ام امتیاز مربوط به راس ‎$i$‎ ام است.
• و در نهایت در یک خط ‎$(1 \leq s,t \leq n)$ $(s \neq t)$ (اول ‎$s$‎ و بعد ‎$t$‎) آمده است که ‎$s$‎ و ‎$t$‎ به ترتیب نشان‌دهنده‌ی شماره راس پایگاه بازیکن اول و راس پایگاه بازیکن دوم هستند‎.‎
• گراف داده شده همبند است‎.‎

• خروجی شامل ‎$k$‎ خط است که هر خط یا ‎$1$‎ است یا ‎$2$‎ و یا ‎$0$‎.
• اگر خط ‎$i$‎ ام ‎$1$‎ بود یعنی بلوک ‎$i$‎ ام ورودی استراتژی برد با نفر اول است. اگر ‎$2$‎ بود یعنی استراتژی برد با نفر دوم است و اگر صفر بود یعنی اگر هر دو بازیکن بهترین بازی را انجام دهند بازی تساوی می‌شود.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد

‎