+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در زمان **دوره ۱۰۲۸ ایا** ربات‌ها آنقدر پیشرفت کرد‌ه بودند که بتوانند کنترل جهان را بدست بگیرند! (همانطور که پیشگوی بزرگ **دوره ۲۸ ایا** پیش‌بینی کرده بود). برای مقابله با این تهدید بزرگ تیم زبده‌ای از **دوره ۱۰۲۸ ایا** دست‌‌بکار شدند. طبق آخرین اخبار رسیده از جاسوس‌هایمان، ربات‌ها توانایی تولید ربات‌های دیگر را پیدا کرده‌اند. اما از آنجایی که اینکار برایشان سخت است، یک ربات به تنهایی نمی‌تواند یک ربات دیگر بسازد و هر ربات جدید را دقیقا دو ربات با همکاری یکدیگر می‌سازند. همچنین می‌دانیم که یک ربات جدید، دو ربات تولید‌کننده‌اش را پدر خود می‌داند. **دوره ۱۰۲۸ ایا** به‌تازگی حمله موفقیت‌آمیزی به مقرر ربات‌ها داشته‌اند و طی این عملیات دو تا از ربات‌ها به نام $a$ و $b$ را گروگان گرفته‌اند و حالا می‌خواهند از ربات $a$ بازجویی کنند! از آنجایی که ربات $a$ دهنش قرص قرص است، **دوره ۱۰۲۸ ایا** تصمیم گرفتند به روش‌های سخت تر رو بیاورند و ربات $a$ را تهدید به کشتن ربات $b$ کنند. (در حقیقت **دوره ۱۰۲۸ ایا** مهربان‌تر از این حرف‌ها هستند و هرگز حاضر نخواهند شد به $b$ آسیبی وارد کنند). حالا **دوره ۱۰۲۸ ایا** برای اینکه بفهمند تهدیدشان چقدر کارساز خواهد بود نیاز دارند کوتاه‌ترین رابطه فامیلی $a$ با $b$ را بدانند. # ورودی در سطر اول $n$ (تعداد کل ربات‌ها) ، $a$ و $b$ داده می‌شود. در $n$ سطر بعد دو عدد $par1_i$ و $par2_i$ که سازنده‌های ربات $i$ ام هستند، می‌آیند. همچنین اگر آن ربات توسط انسان‌ها تولید شده بود، به جای هر دو $-1$ می‌آید. $$1 \le n \le 100\ 000$$ $$-1 \le par1_i,par2_i \le i-1$$ $$ par1_i \neq par2_i $$ $$ a \neq b $$ # خروجی **کوتاه‌ترین** نسبت $a$ با $b$ را از لحاظ تعداد کلمات چاپ کنید. اگر چندین کوتاه‌ترین رابطه وجود داشت شما باید رابطه‌ای که از لحاظ **ترتیب لغت‌نامه‌ای بزرگترین** است را چاپ کنید! توجه کنید که رابطه‌ای که در خروجی بیان می‌شود باید از زبان $a$ باشد.به عنوان مثال اگر $b$ سازنده $a$ باشد جواب `pedar` است. در صورتیکه $a$ و $b$ با هم هیچ رابطه فامیلی نداشتند فقط باید ‍‍`No relationship!` را چاپ کنید. رابطه‌هایی که در خروجی می‌آیند: | رابطه | خروجی | معنی | |-------|----------|------------| | پدر | pedar | سازنده | | پسر | pesar | ساخته شده | | برادر | baradar | پسر پدر | | عمو | amoo | برادر پدر | # مثال ## ورودی نمونه ۱ ``` 10 8 4 -1 -1 -1 -1 -1 -1 2 1 -1 -1 1 5 -1 -1 1 2 6 3 5 2 ``` ## خروجی نمونه ۱ ``` 1 baradar ``` ## ورودی نمونه ۲ ``` 9 9 6 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 5 4 5 3 7 2 8 1 ``` ## خروجی نمونه ۲ ``` 2 amoo pedar ``` ## ورودی نمونه ۳ ``` 8 8 1 -1 -1 -1 -1 1 2 1 2 3 4 3 4 5 6 5 6 ``` ## خروجی نمونه ۳ ``` 3 pedar pedar pedar ``` ## ورودی نمونه ۳ ``` 2 1 2 -1 -1 -1 -1 ``` ## خروجی نمونه ۳ ``` No relationship! ```

حل سؤال در بانک سؤالات