یک جدول شطرنجی $n\times m$ به شما داده شده که روی آن تعداد خط کشیده شده است. هر خط دو خانه‌ی مجاور را از هم جدا می‌کند. قرار است که بر روی خانه‌های این جدول دومینو بگذارید؛ هر دومینو دو خانه‌ی مجاور را می‌پوشاند. اگر بین دو خانه‌ی مجاور خط کشیده نشده باشد، می‌توانید روی آن‌دو یک دومینو قرار دهید. شما باید یک چیدمان از دومینوها را ارائه دهید به طوری که روی هر خانه‌ای دقیقا یک دومینو باشد.

این یک مسئله خروجی تنها می‌باشد. لذا فایل‌های $dom1.in$، $dom2.in$، … و $dom20.in$ به شما داده شده‌اند. شما باید فایل‌های خروجی $dom1.out$، $dom2. out $، … و $dom20.out$را بسازید. ارسال شما در این مسئله یک آرشیو (با قالب $ZIP$ یا $tar-gzip$) می‌باشد که شامل تام فایل‌های خروجی بدون هیچ‌گونه زیرشاخه‌ای است. لازم نیست که همه‌ی خروجی‌ها را در آٰرشیو قرار دهید و اگر نتوانستید برخی از موارد را حل کنید، کافی است که مواردی را که حل نموده‌اید، در آرشیو ارسال جای دهید. اندازه‌ی آرشیو ارسالی نمی‌تواند بیش از ۳۰۰ کیلوبایت باشد. ساختار فایل‌های ورودی و خروجی‌هایی که شما باید تولید کنید، در ادامه آمده است.

سطر نخست فایل ورودی شامل دو عدد $n$ و $m$ است: $n$ تعداد سطرها و $m$ تعداد ستون‌های جدول است؛ $m\leq 100$، $1\leq n$ و $mn$‌ زوج می‌باشد. خانه‌های جدول از ۱ تا $mn$ شماره‌گذاری شده‌اند. شماره‌ی خانه‌ی $i$ام در سطر $j$ام $(j-1).m+i$ خواهد بود (به ازای $1\leq j \leq n$ و $1\leq I \leq m$).

سطر دوم حاوی عدد صحیح $0\leq l\leq 5000$ است. هر یک از $l$ سطر بعدی دارای دو عدد صحیح است؛ به ازای هر $i=1,…,l$، سطر $i+2$ام اعداد $p_i$ و $q_i$ را دارد که $q_i\leq nm$، $1\leq p_i$، $p_i$ و $q_i$ شماره‌ی دو خانه‌ی مجاورند و نشان‌دهنده‌ی وجود یک خط بین این دو خانه است.

فایل خروجی باید دارای $\frac{nm}{2}$ سطر باشد که چیدمان دومینوها را نشان دهد؛ هر دومینو در یک سطر. هر سطر حاوی دو عدد صحیح است: شماره‌ی دو خانه‌ی مجاور که باید روی آن‌ها یک دومینو قرار داد. ترتیب دومینوها مهم نیست. به علاوه اگر پاسخ‌ها‌ی متفاوتی وجود دارند، فرقی نمی‌کند که کدام‌یک را تولید می‌کنید.

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

• سوال بعد
• سوال قبل