فرض کنید $T_1$ و $T_2$ دو درخت ریشه‌دار باشند که در هرکدام به هر راس یک عدد به نشانه‌ی برچسب آن راس نسبت داده شده باشد و هر راس حداکثر دو فرزند داشته باشد. درخت $T_1$ زیردرخت $T_2$ است اگر نگاشت یک‌به‌یک $f$ از مجموعه‌ راس‌های $T_1$ به مجموعه راس‌های $T_2$ وجود داشته باشد به طوری که:

• به ازای هر راس $v$ از $T_1$، برچسب $v$ با برچسب $f(v)$ یکسان باشد.
• به ازای هر دو راس $v$ و $w$ از $T_1$، $f(v)$ از اجداد $f(w)$ باشد اگر و تنها اگر $v$ از اجداد $w$ باشد.

برنامه‌ای بنویسید که $k$‌درخت $T_2،T_1$،… و $T_k$ با شرایط گفته‌ شده را از ورودی دریافت کند و تعیین کند که کدام یک زیردرخت دیگری است.

خط نخست فایل ورودی شامل عدد $k$ است. درخطوط بعدی، مشخصات درختها به ترتیب به شکل ذیل آمده است. مشخصات هر درخت $n$ راسی در $n+1$ خط توصیف می‌شود: خط اول $n$ و شماره‌ی راس ریشه‌ی درخت، خط دوم $n$ عدد به نشانه‌ی برچسب راس‌ها با حفظ ترتیب و $n-1$ خط بعد نیمه‌ی فوقانی ماتریس مجاورت گراف را در بر دارد.

در فایل خروجی ماتریس $M_{n\times n}$ را در $n$ خط با لحاظ فاصله بین درایه‌های هر سطر آن چاپ کنید. اگر درخت $T_i$ زیردرخت درخت $T_j$ باشد، درایه‌ی $M_ij$ را برابر یک و در غیر این صورت، برابر صفر قرار دهید. فرض کنید مقادیر $n$ و $k$ از ۱۰۰ بیش‌تر نیست. برچسب راس‌ها هم از بین اعداد قابل ذخیره‌سازی در یک متغیر از نوع Integer انتخاب می‌شوند.

• سوال بعد
• سوال قبل