Processing math: 52%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۶:عملی:سوال ۶

درخت

آقای ‎«نون»‎ در آرشیو برنامه‌های زمان المپیادش یک فایل متنی پیدا کرده است‎!‎

‎در سطر اوّل این فایل یک عدد طبیعی ‎t‎ نوشته شده‌است و پس از آن ‎t‎ بلوک از اعداد بدین صورت قرار گرفته‌اند که در سطر اوّل هر بلوک، یک عدد طبیعی ‎e‎ نوشته شده و بعد از آن دقیقاً ‎e‎ زوج عدد صحیح آمده است.

آقای ‎«نون»‎ حدس می‌زند این فایل یال‌های ‎t‎ تا درخت ریشه‎‌دار (یک درخت ریشه‌دار، درخت جهت‌داری است که در آن فقط و فقط از یک رأس ‎(ریشه)‎ می‌توان به هر یک از رئوس دقیقاً یک مسیر جهت‌دار یافت‎) است‎!‎

آیا حدس آقای ‎«نون»‎ درست است؟‎!‎

ورودی

  • در سطر اوّل ورودی، ‎t‎ تعداد بلوک‌های ورودی آمده‌است. سپس در هر بلوک، ابتدا یک عدد e‎‎، تعداد یال‌های آن بلوک آمده است.
  • پس از آن در هر یک از ‎e‎ سطر بعدی، دو عدد ‎x y‎ آمده است که به معنی وجود یک یال جهت‌دار از ‎x‎ به y‎ است.
  • می‌توانید فرض کنید که در صورتی که یال‌های ورودی تشکیل یک درخت بدهند، رئوس درخت شماره‌های ‎1‎ تا ‎e+1‎ را خواهند داشت؛ امّا لزومی ندارد که ریشه (در صورت وجود) رأس شماره‌ی یک باشد.
  • 1 \leq t \leq 10‎.
  • 1 \leq e \leq 1,000,000‎.
  • ‎‎ اعداد ورودی در تایپ ‎int‎ جا می‌شوند.

خروجی

در ‎t‎ سطر خروجی، به ازای هر یک از بلوک‌های ورودی، در صورتی که آن بلوک یک ‎«درخت ریشه‌دار‎» است، شماره‌ی رأس ریشه را بنویسید. در غیر این‌صورت، عبارت ‎This is not a three!‎ را بنویسید.

محدودیت‌ها

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

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
2
2
3 1
3 2
3
1 2
2 3
1 3
3 ‎
This is not a three!

ابزار صفحه