Sorting Network

Time Limit: 3 Seconds Memory Limit: 16384 KB

‫شبکه‌ی مرتب‌سازی یک مدل انتزاعی ریاضی شامل شبکه‌ای از سیم‌ها و واحدهای مقایسه‌کننده است که برای مرتب‌سازی دنباله‌ای از اعداد از آن استفاده می‌شود. هر مقایسه‌کننده دو سیم را به هم متصل می‌کند و مقادیر را با قرار دادن مقدار کوچکتر روی یکی از سیم‌ها و مقدار بزرگتر روی سیم دیگر، مرتب می‌کند. هر سیم دارای یک مقدار می‌باشد، و هر مقایسه‌کننده دو سیم را به عنوان ورودی و خروجی می‌گیرد. زمانی که دو مقدار وارد مقایسه‌کننده می‌شود، مقایسه‌کننده مقدار کوچکتر را در سیم بالاتر، و مقدار بزرگتر را در سیم پایین قرار می‌دهد. به شبکه‌ای از سیم‌ها و مقایسه‌کننده‌ها که به طور صحیح تمام مقادیر ورودی را به صورت صعودی مرتب کنند یک شبکه ‫مرتب‌سازی گفته می‌شود.
‫شکل زیر (چپ) نشان دهنده‌ی یک شبکه‌ی ‫مرتب‌سازی است. سیم‌ها در این شکل به صورت افقی و مقایسه‌کننده‌ها به صورت عمودی نشان داده شده‌اند. مراحل انجام ‫مرتب‌سازی توسط این شبکه در شکل راست نشان داده شده است. فهم چگونگی صحیح عمل کردن این شبکه ‫مرتب‌سازی آسان است. این را مدنظر داشته باشید که مقایسه‌کننده‌ها مقدار بزرگ را به سیم پایین و مقدار کوچک را به سیم بالا منتقل می‌کنند.

‫

‫هدف این تمرین این است که عملکرد یک شبکه را روی یک دنباله‌ی ورودی شبیه‌سازی کنیم. در ورودی، شبکه و دنباله‌ی اعداد داده می‌شوند. خروجی برنامه تعیین می‌کند که آیا شبکه‌ی داده شده اعداد را به درستی مرتب می‌کند یا نه. توضیح این که لزوماً هر شبکه، به طور صحیح اعداد را مرتب نمی‌کند. مثال‌هایی از حالت‌های درست و نادرست در نمونه‌های زیر ذکر می‌شوند. علاوه بر این، ممکن است در توصیف شبکه‌ی ورودی خطاهایی وجود داشته باشد که برنامه‌ی شما باید آنها را تشخیص دهد. برای توصیف یک شبکه‌ی ورودی، از ماتریسی از کاراکترها استفاده می‌کنیم. به عنوان مثال شبکه‌ی نشان داده شده در شکل فوق توسط ماتریس زیر توصیف می‌شود.

‫

a-c-
-bce
a-de
-bd-

‫هر سطر از ماتریس یک سیم را مشخص می‌کند. هر کاراکتر از یک سطر یا '-' است که نشان‌دهنده‌ی وجود نداشتن مقایسه‌کننده در آن بخش است یا با یک حرف لاتین مشخص می‌شود که در این صورت، باید در یکی (و تنها یکی) دیگر از کاراکترهای آن ستون کاراکتر مشابهی پیدا شود. به این ترتیب، فرض می‌شود یک واحد مقایسه‌کننده بین سیم‌های متناظر آن دو سطر وجود دارد. به عنوان مثال، در توصیف فوق یک مقایسه‌کننده بین دو سیم اول و سوم وجود دارد که با حرف'a'مشخص شده. ستون دوم نیز وجود یک مقایسه‌کننده بین سیم‌های دوم و چهارم است. ترتیب انتقال اعداد از چپ به راست فرض می‌شود. در توصیف داده‌شده از شبکه ممکن است خطاهایی به شرح زیر وجود داشته باشد که برنامه‌ی شما باید آنها را تشخیص دهد:
‫• در یک ستون تنها یک مورد از یک حرف پیدا می‌شود یا این که بیش از دو مورد از آن حرف وجود دارد.
‫• در توصیف شبکه کاراکتری غیر از حروف کوچک لاتین و ’–’ وجود دارد.
‫دقت کنید که دو مقایسه‌کننده در دو ستون مختلف می‌توانند با یک حرف یکسان نمایش داده شوند، چون این امر ابهامی در عملکرد شبکه ایجاد نمی‌کند.

Input

‫خط اول هر مورد آزمون حاوی دو عدد صحیح N و K است که به ترتیب تعداد سطرها و تعداد ستون‌های ماتریس شبکه را مشخص می‌کنند. بعد از آن، N خط پشت سر هم می‌آیند که هر یک از K کاراکتر تشکیل شده‌اند و محتوای کاراکترهای ماتریس را مشخص می‌کنند. سپس در یک خط، N عدد صحیح که به ترتیب روی سیم‌های ١تا N قرار خواهند گرفت ذکر می‌شوند.

Output

‫برای هر تست شما باید یکی از سه کلمه "Sorted" ، "Not Sorted" و "Invalid Network" را به عنوان خروجی چاپ کنید که به ترتیب بیانگر این است که شبکه توانسته اعداد را مرتب کند، نتوانسته اعداد را مرتب کند یا این که شبکه معتبری به عنوان ورودی داده نشده است.

Sample Input

4 4
ac-e
a-de
b-df
bc-f
1 3 2 0

Sample Output

Sorted

Submit