Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۱۳:سوال ۱

تورنمنت

یک تورنمنت n راسی داریم (تورنمنت یک گراف کامل جهت‌دار است) می‌خواهیم یک راس x و یک زیردرخت فراگیر به ریشه‌ی x از این گراف پیدا کنیم که ارتفاع آن حداکثر ۲ است و درجه‌ی ورودی هر راس به‌جز x در آن دقیقا ۱ و درجه‌ی خروجی هر راس به‌جز x‌ در آن حداکثر ۲ باشد.

ورودی

در خط اول فایل ورودی n و در n1 خط بعد نیمه پایین ماتریس مجاورت تورنمنت داده شده است.

خروجی

در صورت وجود جواب برنامه‌ی شما باید در خط اول فایل خروجی شماره‌ی راس x و در n1 خط بعد در هر خط دو عدد بنویسید که عدد اول ابتدا و عدد دوم انتهای یک یال از n1 یال درخت باشد. در غیر این صورت در فایل خروجی No Solution بنویسید.

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

ورودي نمونه خروجي نمونه
4
0
0 1
1 0 1
4
4 1
4 3
3 2

ابزار صفحه