- محدودیت زمان: ۱.۵ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
پس از تلاش‌های ناموفق لیته برای خوشحال کردن فیته، وی تصمیم گرفت خودش و فیته را در برنامه بعدی گروه کوه دانشگاه ثبت‌نام کند تا این سفر چندروزه باعث بهبود روابطشان شود.
برنامه بعدی گروه کوه در منطقه‌ی بقمچگاه برگزار خواهد شد که استراحت‌گاه‌های آن و راه‌های ارتباطی بین آنها مثل یک گراف جهت‌دار هستند. در این گراف:
- از یک استراحتگاه به یک استراحتگاه دیگر حداکثر یک راه مستقیم وجود دارد. (ممکن است بین دو استراحتگاه دو راه متفاوت در خلاف جهت یکدیگر وجود داشته باشد)
- از یک استراحتگاه به خودش راه مستقیمی وجود ندارد.
- ممکن است در گراف دور وجود داشته باشد.
اما دقیقا یک روز قبل از حرکت به سمت بقمچگاه، اخبار ناخوشایندی به لیته می‌رسد مبنی بر این که طی روزهای برنامه در این منطقه ییلاقی شاهد زمین‌لرزه‌ها و پس‌لرزه‌هایی خواهیم بود.
- به طور واضح تر این‌طور خواهد بود که به ازای هر استراحتگاه در بعضی از روزها در آن استراحتگاه لرزشی اتفاقی می افتد. اولین لرزش در یک استراحتگاه یک زمین‌لرزه است و همه‌ی لرزش‌های بعدی پس‌لرزه هستند. ( تفاوت زمین‌لرزه و پس‌لرزه در پایین توضیح داده شده است )
متاسفانه اگر در یکی از استراحت‌گاه‌های این منطقه زمین‌لرزه اتفاق بیفتد، همه افراد ساکن در این استراحتگاه به دیار باقی خواهند شتافت. و اگر در استراحت‌گاهی پس‌لرزه بیاید، افراد ساکن باید به یکی از استراحت‌گاه‌هایی که به آن راه خروج مستقیم دارند فرار کنند. این فرار دقیقا یک روز طول می‌کشد. توجه کنید در صورتی که در استراحت‌گاهی پس‌لرزه بیاید و آن استراحتگاه به استراحتگاه دیگری راه خروج مستقیمی نداشته‌باشد، ناچار جان به جان‌آفرین تسلیم خواهند کرد.
نکته‌ی حائز اهمیت این است که لیته و فیته در این سفر در کنار هم خواهند بود و هر وقت ناچار به فرار شوند، یکی از استراحتگاه های ممکن را باهم انتخاب می‌کنند و به آن‌جا می‌روند. یعنی تا لرزه‌ای رخ ندهد در جای خود ساکن خواهند ماند.
نیمه‌های شب لیته با اتصال به روح مهرسا از زمان همه زمین‌لرزه‌ها و پس‌لرزه‌ها باخبر می‌شود و حالا مدام سوالاتی به ذهنش می‌رسند که اگر در روز $t$-ام اردو در استراحتگاه شماره $x$ باشند، آیا ممکن است تا آخر اردو زنده بمانند یا خیر. طبیعتا شما باید در حل این مسئله به او کمک کنید.
ورودی
سطر اول ورودی شامل سه عدد طبیعی $n$ و $m$ و $q$ است که به ترتیب نشاندهنده تعداد استراحت‌گاه‌ها، تعداد راه‌های یک‌طرفه بین آنها و تعداد سوالات ذهن لیته هستند.$$1 \le n, m, q \le 400\ 000$$ در $i$-امین سطر از $n$ سطر بعد اطلاعات لرزش‌های استراحتگاه شماره $i$ آمده است، به این صورت که در ابتدا عدد $k$ آمده است که نشاندهنده تعداد لرزش‌های شهر $i$ است و به دنبال آن $k$ عدد مثل $t$ به ترتیب صعودی اکید آمده اند که نشاندهنده‌ی روزهایی هستند که در شهر $i$ لرزش اتفاق افتاده است.
- اولین لرزش هر شهر یک زمین‌لرزه است و بقیه لرزش‌ها در آن شهر پس‌لرزه هستند.
- تضمین می‌شود که زمان تمامی لرزش‌ها متفاوت هستند. یعنی در یک زمان در دو استراحتگاه لرزش اتفاق نمی افتد. $$0 \le k \le 400\ 000$$ $$1 \le t \le 10^9$$
- هم‌چنین تضمین می‌شود در مجموع تعداد لرزش ها کمتر مساوی $400\ 000$ می‌باشد.
در هر یک از $m$ سطر بعد دو عدد $v$ و $u$ آمده‌است که نشاندهنده وجود مسیر یک‌طرفه از استراحتگاه شماره $v$ به استراحتگاه شماره $u$ است. $$1 \le v, u \le n$$ در هر یک از $q$ سطر بعد به ترتیب دو عدد $x$ و $t$ آمده‌است که نشاندهنده یکی از سوالات ذهن لیته است. (آیا اگر آنها در روز $t$ در استراحتگاه شماره $x$ باشند می‌میرند یا زنده خواهند ماند) $$1 \le t \le 10^9$$ $$1 \le x \le n$$
خروجی
به ازای هر سوال ذهن لیته، اگر پاسخ سوال این است که زنده خواهند ماند کلمه Alive را چاپ کنید و در غیر این‌صورت کلمه Dead را چاپ کنید.
مثال
ورودی نمونه ۱
4 4 4
2 2 4
3 1 5 7
1 6
1 10
1 2
2 3
3 1
2 4
2 5
2 6
1 4
1 5
خروجی نمونه ۱
Dead
Alive
Dead
Alive
نقشه استراحتگاه مربوط به ورودی نمونه را در شکل زیر می‌بینید.
اگر در زمان ۵ در استراحتگاه ۲ باشند (پرسش اول) قطعا می‌میرند زیرا چه به استراحتگاه ۳ (در زمان ۶) بروند چه استراحتگاه ۴ (در زمان ۱۰) می‌میرند.
اگر در زمان ۶ در استراحتگاه ۲ باشند (پرسش دوم) می‌توانند در زمان ۷ پس لرزه می‌آید و آنها با رفتن به استراحتگاه ۳ زنده می‌مانند. زیرا در زمان ۸ به استراحتگاه ۳ می‌رسند و دیگر زلزله‌ای نمی‌آید.
اگر در زمان ۴ در استراحتگاه ۱ باشند (پرسش سوم) مجبورند به استراحتگاه ۲ بروند و مانند پرسش اول می‌میرند.
اگر در زمان ۵ در استراحتگاه ۱ باشند (پرسش چهارم) زلزله‌ای نمی‌آید و همانجا زنده می‌مانند.
ارسال پاسخ برای این سؤال