درخت
آقای «نون» در آرشیو برنامههای زمان المپیادش یک فایل متنی پیدا کرده است!
در سطر اوّل این فایل یک عدد طبیعی $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! |