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

در همان زمان بود که شی‌کرکس‎ که فرزند کوچک خانواده بود، فهمید از این طریق به قدرت نخواهد رسید و از آن‌وقت شروع به مطالعه کرد تا بتواند سلاحی تولید کند تا برادرش را در این راه شکست دهد و به قدرت برسد. پس از نیم قرن کار بی‌وقفه حالا نوبت شی‌کرکس بود تا به همگی ثابت کند او لیاقت به قدرت رسیدن را داشته است. او می‌خواست با بمب اتمی که ساخته تک‌تک شهرهای کشور را از بین ببرد‎. ‎ کرکس که از این خبر مطلع شده بود، در حال جمع‌آوری نیروی جسمی و فکری بود. شما در قسمت کمک‌های فکری استخدام شده‌اید و وظیفه دارید به سوالات کرکس پاسخ دهید تا او نقشه‌های جنگی خود را به نحو احسن طرح کند. ‎ به شما دو نوع جمله داده می‌شود:

• خبری: شهر ‎$x$‎ام به همراه تمام جاده‌های متصل به آن توسط بمب اتم از بین رفتند.
• سوالی: کم‌ترین فاصله بین دو شهر ‎$x$‎ و ‎$y$‎ در حال حاضر چیست؟‎

• در سطر اول ورودی دو عدد ‎$(1 \leq n \leq 350)$ $(0 \leq m \leq min(200000,\frac{n \times (n-1)}{2}))$‎ نشان دهنده تعداد شهرها و جاده‌ها و سپس ‎$(0 \leq q \leq 200000)$‎ نشان دهنده تعداد سوالات کرکس آمده است‎.‎
• در ‎$m$‎ سطر بعد ‎$3$‎ عدد صحیح آمده است که به معنی وجود جاده دوطرفه بین شهر‌های دو عدد اول با مسافتی برابر عدد سوم است.‎
• در ‎$q$‎ سطر بعد هر کدام یک جمله خبری یا پرسشی آمده‎:‎
  • اگر جمله پرسشی باشد، در ابتدای خط یک علامت سوال آمده و سپس شماره دو شهر که کرکس از شما فاصله آن‌ها را می‌خواهد.‎
  • اگر جمله خبری باشد، در ابتدای خط واژه ‎attacked‎ آمده و سپس شماره شهری که به آن حمله شده است.‎
• تمامی اعداد ورودی بین ‎$0$‎ و ‎$10^6$‎ هستند.

‎ به ازای هر سوالی که از شما پرسیده می‌شود، یک خط در خروجی بنویسید.‎ اگر دو شهر مورد نظر هنوز با یکدیگر در ارتباط بودند کمینه فاصله را چاپ کنید و در غیر این صورت جمله‌ی ‎no path‎ را بنویسید.

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

• سوال بعد