+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۱۰۲۴ مگابایت ---------- مالیات اصلی‌ترین راه تامین درآمد بسیاری از کشور‌ها از جمله کشور‌های پیشرفته است و هزینه‌ی بسیاری از پروژه‌های زیرساختی، عمرانی و حتی حقوق کارمندان دولت، معلمان و ... از طریق دریافت مالیات از کسبه، شرکت‌ها و ... تامین می‌شود. فرار مالیاتی به زبان ساده یعنی مالیات‌دهنده تلاش کند کمتر از میزان واقعی مالیات پرداخت کند. مثلاً فرض کنید یک کاسب در طول سال، ۱۰۰ میلیون تومان سود (مجموع درآمد منهای هزینه‌ها) داشته و با نرخ ۱۵ درصد باید ۱۵ میلیون تومان مالیات بپردازد. حالا اگر این کاسب تلاش کند با روش‌های مختلف میزان سود اصلی خود را کمتر نشان دهد، مالیات کمتری نیز می‌پردازد. به این عمل فرار مالیاتی می‌گوییم. در حال حاضر فرار مالیاتی یک چالش بزرگ در کشور‌های دنیاست، گزارش‌های مختلف نشان می‌دهد در ایران خودمان سالانه بین ۴۰ تا ۱۵۰ هزار میلیارد تومان فرار مالیاتی داریم. یکی از موثرترین راه‌های جلوگیری از فرار مالیاتی در برخی از کشور‌های پیشرفته تحلیل داده‌های مالی به صورت گراف است. به این صورت که تمام داده‌های مالی شامل تراکنش‌ها، خرید و فروش‌ها و مالکیت‌ها را به صورت راس‌های گراف اصلی (گرافی بسیار بزرگ) مدل می‌کنیم و انواع شکل‌هایی که احتمال دارد فرار مالیاتی باشد را به صورت گراف الگو (گرافی بسیار کوچک) مدل می‌کنیم. سپس در گراف اصلی زیرگراف‌هایی که شبیه گراف الگوی فرار مالیاتی باشد را پیدا می‌کنیم. مثال‌های از تخلفات که به راحتی قابل تبدیل به گراف‌های الگو هستند: + کاسبی که در سال گذشته یک آپارتمان با قیمت بالای سه میلیارد تومان و یک خودروی ۵۰۰ میلیون تومانی خریده است اما در اظهارنامه مالیاتی سودش را کمتر از ۵۰ میلیون اعلام کرده است. + شرکتی که در اظهارنامه مالیاتی ضررده اعلام شده اما پاداش آخر سال مدیران آن صد‌ها میلیون تومان بوده است. در ادامه حالت ساده شده‌ی این مسئله آورده شده، که حل آن می‌تواند مقدمه‌ای بر حل مسئله‌ی فرار مالیاتی باشد، پس تلاش خود را به کار ببرید، این گوی و این میدان! ---------- در این مسئله یک گراف اصلی و یک گراف الگو به شما داده می‌شود. حال شما می‌بایست تعداد زیر گراف‌های موجود در گراف اصلی را پیدا کنید به طوری که این زیرگراف‌ها مشابه گراف الگو باشند. (برای فهم بهتر مسئله به شکل‌های پایین صفحه مراجعه کنید) **توجه**: برنامه‌ی شما حتما باید به زبان **$Java$** باشد و شما مجاز به ایجاد هر گونه کلاس، تابع، اینترفیس و ... هستید. ### نکات مهم: 1. گراف‌ها رنگی و جهت‌دار هستند. 2. گراف الگو ضعیفا همبند است. (در صورتی که جهت یال‌ها را در نظر نگیریم، گراف ما همبند است) 3. بین هر دو راس گراف الگو حداکثر یک یال در هر جهت وجود دارد. 4. هر راس گراف شامل یک ‌‌‌شناسه یکتا و یک رنگ است. 5. هر یال گراف شامل یک شناسه راس مبدا و یک شناسه راس مقصد است. # ورودی ### اطلاعات گراف اصلی 1. در خط اول ورودی ‌‌$n_1$ (تعداد راس‌های گراف اصلی) وارد می‌شود. 2. سپس در $n_1$ خط بعدی یک رشته (شناسه راس) و $a_i$ (شماره رنگ راس‌) برای راس‌های گراف اصلی با یک فاصله از هم وارد می‌شوند. 3. سپس مقدار ‌‌$m_1$ (تعداد یال‌های گراف اصلی) وارد می‌شود. 4. سپس در $m_1$ خط بعدی دو رشته برای شناسه‌ی راس مبدا و شناسه‌ی راس مقصد یال‌های گراف اصلی با یک فاصله از هم وارد می‌شوند. ### اطلاعات گراف الگو 5. در خط بعد ‌‌$n_2$ (تعداد راس‌های گراف الگو) وارد می‌شود. 6. سپس در $n_2$ خط بعدی یک رشته (شناسه راس) و $b_i$ (شماره رنگ راس‌) برای راس‌های گراف الگو با یک فاصله از هم وارد می‌شوند. 7. سپس مقدار ‌‌$m_2$ (تعداد یال‌های گراف الگو) وارد می‌شود. 8. سپس در $m_2$ خط بعدی دو رشته‌ی شناسه‌ی راس مبدا و شناسه‌ی راس مقصد یال‌های گراف الگو با یک فاصله از هم وارد می‌شوند. $$1 \le n_1 \le 30\ 000$$ $$1 \le a_i \le 4$$ $$1 \le m_1 \le 10*n_1$$ $$1 \le n_2 \le 5$$ $$1 \le b_i \le 4$$ $$1 \le m_2 \le 20$$ # خروجی خروجی تنها شامل یک عدد است که تعداد زیرگراف‌های موجود از گراف اصلی (شبیه به گراف الگو) را نشان می‌دهد. # مثال ## ورودی نمونه ۱ ``` 5 1 1 2 2 3 2 4 2 5 2 8 1 2 1 5 2 3 2 4 2 5 3 4 5 3 5 4 3 A 1 B 2 C 2 2 A B B C ``` ## خروجی نمونه ۱ ``` 5 ``` <details> <summary>توضیحات نمونه‌ی ۱</summary> گراف اصلی نمونه ۱:  گراف الگو نمونه ۱:  با توجه به جدول زیر تعداد زیرگراف‌های مشابه گراف الگو در گراف اصلی، ۵ تاست، بنابراین عدد ۵ در خروجی چاپ می‌شود. | |راس A|راس B|راس C| |:-------:|:---:|:---:|:---:| |زیرگراف ۱|راس ۱|راس ۲|راس ۳| |زیرگراف ۲|راس ۱|راس ۲|راس ۴| |زیرگراف ۳|راس ۱|راس ۲|راس ۵| |زیرگراف ۴|راس ۱|راس ۵|راس ۳| |زیرگراف ۵|راس ۱|راس ۵|راس ۴| </details> ## ورودی نمونه ۲ ``` 5 1 1 2 2 3 2 4 2 5 2 4 1 2 1 3 1 4 1 5 3 A 1 B 2 C 2 2 A B A C ``` ## خروجی نمونه ۲ ``` 12 ``` <details> <summary>توضیحات نمونه‌ی ۲</summary> گراف اصلی نمونه ۲:  گراف الگو نمونه ۲:  با توجه به جدول زیر تعداد زیرگراف‌های مشابه گراف الگو در گراف اصلی، ۱۲ تاست، بنابراین عدد ۱۲ در خروجی چاپ می‌شود. | |راس A|راس B|راس C| |:--------:|:---:|:---:|:---:| |زیرگراف ۱ |راس ۱|راس ۲|راس ۳| |زیرگراف ۲ |راس ۱|راس ۲|راس ۴| |زیرگراف ۳ |راس ۱|راس ۲|راس ۵| |زیرگراف ۴ |راس ۱|راس ۳|راس ۲| |زیرگراف ۵ |راس ۱|راس ۳|راس ۴| |زیرگراف ۶ |راس ۱|راس ۳|راس ۵| |زیرگراف ۷ |راس ۱|راس ۴|راس ۲| |زیرگراف ۸ |راس ۱|راس ۴|راس ۳| |زیرگراف ۹ |راس ۱|راس ۴|راس ۵| |زیرگراف ۱۰|راس ۱|راس ۵|راس ۲| |زیرگراف ۱۱|راس ۱|راس ۵|راس ۳| |زیرگراف ۱۲|راس ۱|راس ۵|راس ۴| </details> ## ورودی نمونه ۳ ``` 2 1 1 2 1 2 1 2 2 1 2 A 1 B 1 1 A B ``` ## خروجی نمونه ۳ ``` 2 ``` <details> <summary>توضیحات نمونه‌ی ۳</summary> گراف اصلی نمونه ۳:  گراف الگو نمونه ۳:  با توجه به جدول زیر تعداد زیرگراف‌های مشابه گراف الگو در گراف اصلی، ۲ تاست، بنابراین عدد ۲ در خروجی چاپ می‌شود. | |راس A|راس B| |:-------:|:---:|:---:| |زیرگراف ۱|راس ۱|راس ۲| |زیرگراف ۲|راس ۲|راس ۱| </details>

حل سؤال در بانک سؤالات