Masoud's Dominoes 2

Time Limit: 1 Second    Memory Limit: 65536 KB

بازی سوال قبل را درنظر بگیرید. این بار مسعود می‌خواهد آن مسیر همبند شامل تمام دومینوهای داده شده را پیدا کند. در این مسئله تعدادی از مهره‌ها به عنوان ورودی داده می‌شود که قطعا می‌توان با آنها حداقل یک مسیر شامل تمام مهره‌ها ساخت به شرط اینکه دو هر دو مهره‌ی مجاور، عددی یکسان در وجه‌های مجاورشان داشته باشند. (همان شرایط سوال قبل) همچنین مسعود برای هر حالت یک ارزش تعریف می‌کند، به این شکل که از ابتدای مسیر عددهای هر مهره را به شکل یک رقم در مبنای ۱۷ میبیند (اول عدد سمت ابتدا و سپس عدد سمت انتهای مسیر) و با کنار هم قرار دادن این 2n رقم (۲ برابر مهره‌ها عدد داریم) یک عدد در مبنای ۱۷ می‌سازد که ارزش این مسیر است. (پر ارزش ترین رقم این عدد، عددی از وجه مهره‌ی اول است که در مجاورت مهره‌ی دیگری نیست)

حال وظیفه‌ی شما این است که از بین مسیرهای موجود، کم‌ارزش ترین را چاپ کنید.

Input

فرمت ورودی مانند سوال قبل است، یعنی برای هر تست در خط اول عدد n < 600 مشخص کننده‌ی تعداد مهره‌ها می‌آید و در خط بعد n زوج مرتب می‌آیند که مشخص کننده‌ی اعداد دوطرف هر مهره هستند.

Output

Sample Input

3
1 0 1 2 2 1
4
0 1 0 1 0 1 1 0

Sample Output

0 1 1 2 2 1
0 1 1 0 0 1 1 0