+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت ---------- شیرین عسل وقتی به خانه‌ی یار رسید بر خلاف تصور همگان (به ویژه یار) به یاداشت گذاشتن بسنده کرد!! او متوجه شد که اگر برای یار یادداشت بگذارد توسط یک ماشین برخی از کاراکترهای یاداشت پاک می‌شوند و سپس یاداشت به دست یار می‌رسد. شیرین عسل می‌خواهد کوتاه‌ترین یادداشتی را بنویسد که پس از حذفیات یادداشت مورد نظر شیرین عسل باقی‌بماند. این ماشین به این صورت کار می‌کند که با وضعیت $1$ شروع می‌کند و به ترتیب حروف نامه را بررسی می‌کند و با توجه به وضعیت ماشین و قوانینی که یار برای ماشین تعریف کرده است در بررسی هر یک از حروف یکی از کارهای زیر را انجام می‌دهد: 1. اگر ماشین در وضعیت $v$ باشد و حرفی که ماشین در حال بررسی آن است برابر $c$ باشد و قانونی مانند `v u c` وجود داشته باشد آن حرف پاک می‌شود و وضعیت ماشین به $u$ تغییر می‌کند ($v$ و $u$ اعداد طبیعی و نمایانگر شماره وضعیت هستند و $c$ یک حرف کوچک انگلیسی است). 2. اگر هیچ قانونی مانند `v u c` وجود نداشته باشد وضعیت ماشین تغییر نمیکند و آن حرف پاک نمی‌شود و دستگاه به بررسی حرف بعدی می‌پردازد. طول کوچک‌ترین یاداشتی که شیرین عسل می‌تواند بنویسد را به او بگویید. شکل برای نمونه ۱  # ورودی در سطر اول ورودی دو عدد طبیعی $n$‌ و $m$ آمده است که به ترتیب نمایانگر تعداد وضعیت‌های ماشین و تعداد قوانین است. در خط بعدی رشته‌ی $s$ شامل حروف کوچک انگلیسی آمده است که نمایانگر متن یادداشت مورد نظر شیرین عسل است. سپس در $m$ ‌خط بعدی در هر خط توضیح یکی از قوانین به صورت `v u c` آمده است. $$ 1 \le n \le 1\ 000 $$ $$ 1 \le m \le 26\ 000 $$ $$ 1 \le |s| \le 1\ 000 $$ $$ 1 \le v , u \le n $$ تضمین می‌شود هیچ دو قانونی با $v$ و $c$ یکسان وجود ندارند. # خروجی در تنها سطر خروجی جواب مسئله را چاپ کنید و اگر هیچ یادداشتی نمی‌تواند به شیرین عسل کمک کند $-1$ را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 2 baba 1 2 a 2 1 b ``` ## خروجی نمونه ۱ ``` 7 ``` ## ورودی نمونه ۲ ``` 3 3 yar 1 2 a 2 3 a 3 1 a ``` ## خروجی نمونه ۲ ``` -1 ```