+ محدودیت زمان: ۶ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- مسئله‌ای به شما داده شده است که بایستی به صورت یک مسئله $CSP$ آن را فرموله کرده و پیاده‌سازی نمایید. فرض کنید گرافی در اختیار داریم که گره‌های آن می‌توانند هر یک از اشکال مثلث، مربع، پنج ضلعی، شش ضلعی و یا دایره باشند. می‌خواهیم به هر گره از این گراف، یک عدد بین ١ تا ٩ نسبت دهیم به صورتی که شروط زیر برقرار باشند: + عدد منتسب به هر گره مثلثی شکل، برابر سمت چپ ترین رقم حاصل ضرب اعداد منتسب به گره‌های مجاور آن باشد. + عدد منتسب به هر گره به شکل مربع، برابر سمت راست ترین رقم حاصل ضرب اعداد منتسب به گره‌های مجاور آن باشد. + عدد منتسب به هر گره به شکل پنج ضلعی، برابر سمت چپ ترین رقم حاصل جمع اعداد منتسب به گره‌های مجاور آن باشد. + عدد منتسب به هر گره به شکل شش ضلعی، برابر سمت راست ترین رقم حاصل جمع اعداد منتسب به گره‌های مجاور آن باشد. + محدودیتی برای گره‌های دایره‌ای شکل وجود ندارد. شکل یک گراف نمونه با اعداد منتسب شده به هر گره را نشان می‌دهد. از شما خواسته شده است تا با دریافت مشخصات گراف، اعداد منتسب به گره‌های آن را پیدا کنید.  # ورودی خط اول ورودی عدد $T$ است که تعداد تست‌ها را نشان می‌دهند. خط اول هر تست، شامل اعداد $V$ و $E$ است که اولی نشان دهنده تعداد گره‌ها و دومی نشان دهنده تعداد یال‌های گراف است. در خط بعد $V$ کاراکتر از بین یکی ͬاز کاراکترهای `T`برای مثلث، `S` برای مربع، `P` برای پنج ضلعی، `H` برای شش ضلعی و `C` برای دایره، که با یک فاصله از هم جدا شده‌اند می‌آید که کاراکتر $i$ام، شکل گره $i$ام را مشخص می‌کند (0 ≥ $i$). پس از آن، $E$ خط به صورت ‍‍`i j` می‌آید. که نشان می‌دهد یالی میان گره $i$ام و گره $j$ام وجود دارد. نمونه ورودی متناظر با شکل در ادامه آمده است. # خروجی به ازای هر تست، یک خط خروجی می‌آید که شامل $V$ عدد بین ١ تا ٩ است که با فاصله از هم جدا شده اند و عدد $i$ام، مقدار منتسب به گره $i$ام را نشان می‌دهد. # مثال ## ورودی نمونه ۱ ``` 1 9 8 C P H S S H H T C 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 ``` ## خروجی نمونه ۱ ``` 9 1 7 6 8 3 5 2 4 ```