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

سیب که رنگی نیست، تخم مرغ!

امین با روحیه گرافی خود سعی کرد از ظرف تخم مرغ رنگی روی سفره هفت‌سین سوال طرح کند. او تعداد تخم مرغ رنگی‌های توی ظرف را که $n$ بود شمرد و گراف $G$ را با $n$ راس ساخت. سپس بین هر دو تخم مرغی که با یکدیگر در تماس بودند یال کشید. می‌دانیم رنگ تخم مرغ‌ها با یکدیگر متفاوت است. سپس به ازای هر تخم مرغ لیستی درست کرد که شامل رنگ همان تخم مرغ و رنگ تمام تخم مرغ‌های مجاور با آن در گراف $G$ بود.

‌
سیب نماد سلامتی و زیبایی است.

علی که بسیار شیطون است، همه تخم مرغ‌ها را بی‌رنگ کرد و زیبایی آن‌ها را از بین برد. امین از این اتفاق خوشحال نیست. او می‌خواهد تخم مرغ‌ها را دوباره رنگ کند و ظرف تخم مرغ رنگی‌ها به شکل قبلی خود برگردد. با داشتن گراف $G$ و لیست‌هایی که امین برای هر تخم مرغ درست کرده است، تخم مرغ‌ها را بازآرایی کنید.

ورودی

در سطر اول دو عدد صحیح $n$ و $m$، تعداد تخم مرغ‌ها و تعداد یال‌های میان رئوس متناظر تخم مرغ‌ها به ترتیب می‌آیند.

در هر یک از $m$ سطر بعدی، دو عدد صحیح $v$ و $u$ می‌آیند که یال‌های گراف $G$ را مشخص می‌کنند.

در سطر $i$-ام از $n$ سطر بعدی، $d_i + 1$ عدد صحیح می‌آیند که لیست مربوط به تخم مرغ $i$-ام را مشخص می‌کنند. $d_i$ تعداد تخم مرغ‌های مجاور تخم مرغ $i$-ام است. تضمین می‌شود رنگ‌ها عددی بین $1$ تا $n$ هستند. همچنین تضمین می‌شود حداقل یک حالت برای رنگ‌آمیزی تخم مرغ‌ها وجود دارد.

$$1 \leq n, m \leq 1 , 000$$

خروجی

در تنها سطر خروجی $n$ عدد چاپ کنید که رنگ تخم مرغ‌ها را نشان می‌دهد. در صورتی که چندین حالت برای رنگ‌آمیزی تخم مرغ‌ها وجود داشت، یکی را به دلخواه چاپ کنید.

مثال‌ها

ورودی نمونه ۱

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

خروجی نمونه ۱

2 3 4 1