دیرینه‌شناسان پس از تحقیقات انجام شده بر روی گونه‌ای از آبزیان منقرض شده به نام «سیوتابا»، متوجه ساختار ژنتیکی پیچیده‌ی این موجود شدند. هر یک از این آبزیان می‌تواند یک ژن جدید که با شماره‌ای بین $1…n$ نشان داده می‌شود، ایجاد کند و این ژن به اضافه ژن‌های دیگر آن سیوتابا به تمام فرزندان او، به ارث خواهد رسید. همچنین یک سیوتابا می‌تواند ژن جدیدی ایجاد نکند که در این حالت ژن‌های پدر دقیقا به فرزندانش انتقال خواهد یافت. با تحقیقات این دانشمندان نقشه‌ی ژنتیکی $m$ سیوتابا به دست آمد که هیچ‌کدام فرزندی نداشتند. نقشه‌ی ژنتیکی هر سیو‌تابا با دنباله‌ای از اعداد صفر و یک بیان می‌شود که هر ۱ در مکان $i$ ام گویای وجود ژن $i$ در مجموعه ژن‌های آن سیوتاباست. می‌دانیم اگر یکی از سیوتاباها ژنی را ایجاد کند، آن ژن در انحصار آن سیوتابا خواهد بود و هیچ سیوتابای دیگری قادر به ایجاد آن ژن نخواهد بود. و از طرف دیگر، تا وقتی که سیوتابا فرزندی ایجاد نکرده است، نمی‌تواند ژن جدیدی ایجاد کند.

وظیفه

با توجه به این تو ضیحات وظیفه‌ی شما این است که با خواندن نقشه‌ی ژنتیکی $m$ سیوتابا، درخت وراثت آن‌ها را پیدا کنید. این درخت از $m$ سیوتابای فرزند و $k$ سیوتابای دیگر تشکیل شده و پدران هر یک از این سیوتاباها تا سیوتابای اولیه در درخت مشخص شده است. سیوتابای اولیه گونه‌ای از این آبزی است که مجموعه ژن‌های او تهی است و پدری برای او نمی‌توان متصور شد. لازم به ذکر است که درختان وراثت گوناگونی که شرط مسئله را داشته باشند می‌توان در نظر گرفت. همچنین $k$ می‌تواند مقادیر مختلفی را اختیار کند.

توضیحات

چون در این برنامه حجم فایل ورودی بزرگ است به شما یک کتابخانه داده می‌شود. در ضمن یک فایل هم به شما داده می‌شود، که برنامه‌ی شما با آن compile خواهد شد. شما باید ۳ تابع زیر را به ترتیب هر کدام را دقیقا یک بار فراخوانی کنید.

• (int get_m(void که عدد $m$ را به شما می‌دهد.
• (int get_n(void که عدد $n$ را به شما می‌دهد.
• (Array get_gens(void که ساختار ژن‌ها را به شما می‌دهد.

Array یک type است که تعریف آن در فایل کتاب‌خانه نوشته شده است. می‌توانید برای توضیحات بیش‌تر به کتاب‌خانه مراجعه کنید.

در سطر اول ورودی اعداد $m$ و $n$ آمده‌اند که با یک فاصله از هم جدا شده‌اند و در $m$ سطر بعد، در هر سطر یک دنباله‌ی $n$ تایی از صفر و یک، (بدون هیچ فاصله‌ی اضافی) که بیانگر نقشه‌ی ژنتیکی یکی از سیوتاباهاست داده شده است.($m,n \leq 1333$)

دقت کنید فایل ورودی توسط کتاب‌خانه‌ی ما خوانده می‌شود به همین دلیل باید دقیقا به فرمت گفته شده ساخته شود. در ضمن شما می‌توانید فرض کنید زمانی که کتاب‌خانه‌ی ما صرف خواندن فایل ورودی می‌کند کم‌تر از ۰.۱ ثانیه است. بدیهی است که شما باید فایل ورودی را در شاخه‌ای که برنامه‌ی خود را اجرا می‌کنید قرار دهید.

در خط اول خروجی ابتدا عدد $k$‌را بنویسید که تعداد سیوتاباهای اضافه شده برای کامل کردن درخت وراثت است. در خط دوم $k$ عدد بین ۱ و $n$ نوشته شود که اشاره به شماره‌ی ژنی است که هر یک از $k$‌ گونه‌ی پدر در انحصار دارد و ایجاد می‌کند. اگر یکی از گونه‌ها ژنی ایجاد نمی‌کند عدد ۱- را بنویسید. و در خط سوم $k+m$ عدد نوشته شود که $k$ عدد اول پدر $k$ گونه ژن سطر بالا را مشخص می‌کند و $m$ عدد بعدی پدر هر یک از $m$ گونه‌ی فرزند را، به همان ترتیبی که در ورودی ظاهر شده‌اند، مشخص می‌کند. توجه کنید که تمامی اعداد سطر سوم اعدادی بین ۱ و $k$ هستند که مشخص‌کننده‌ی شماره‌ی پدر هر یک از گونه‌هاست که این شماره بر اساس ترتیب ظاهر شدن سیوتاباها در سطر دوم خروجی مشخص می‌شوند. پدر سیوتابای اولیه را با ۱- نشان می‌دهیم.($k\leq 3\times n$)

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

• سوال بعد