Marşrutlaşdırma#1258

Marşrutlaşdırma

1 saniyə

128 meqabayt

Asan

Siz Performans Hesablama üzrə İnanılmaz Əməkdaşlıq təşkilatında mühəndis kimi çalışırsınız və oradakı kompüterlər üçün rabitə şəbəkəsinin dizaynına cavabdehsiniz. Şəbəkə $2 n - 1$ 2n-1 sətirli düzbucaqlı massividə qurulub, hər bir sətirdə $2^{n - 1}$ 2^{n-1} kommutator var. Kommutator iki giriş naqili, $X$ və $Y$ , və iki çıxış naqili, $X^{'}$ X' və $Y^{'}$ Y', olan qurğudur. Kommutator söndürüldükdə, $X$ girişindən gələn məlumat $X^{'}$ X' çıxışına, $Y$ girişindən gələn məlumat isə $Y^{'}$ Y' çıxışına ötürülür. Kommutator yandırıldıqda isə, $X$ $Y^{'}$ Y' çıxışına, $Y$ isə $X^{'}$ X' çıxışına birləşdirilir. Əlavə olaraq, ən yuxarı və ən aşağı sətirlərdə $2^{n}$ 2^n kompüter var və onların arasında cüt-cüt mesaj göndərmək lazımdır. İki fərqli mənbədən gələn məlumat eyni naqildən istifadə edə bilməz, lakin hər iki məlumat müxtəlif girişlərdən eyni kommutatordan keçə bilər.

Siz ehtiyaclarınıza ən yaxşı cavab verən şəbəkənin Benes topologiyasına malik olduğuna qərar vermisiniz. $1$ -Benes şəbəkəsi sadəcə bir kommutatordan ibarətdir. $n > 1$ n > 1 üçün, $n$ -Benes şəbəkəsi aşağıdakı kimi rekursiv qurula bilər:

• Birinci (yuxarı) sətirdə $2^{n - 1}$ 2^{n-1} kommutator var; $j$ -ci kommutator ( $0 \leq j < 2^{n - 1}$ 0 \leq j < 2^{n-1}) $2 j$ və $2 j + 1$ 2j+1 nömrəli kompüterlərdən məlumat qəbul edir (yuxarı və aşağı sətirlərdəki kompüterlər $0$ -dan $2^{n} - 1$ 2^n - 1-ə kimi sağa doğru nömrələnir).

• Birinci və ikinci sətirdəki kommutatorlar arasında çıxış naqillərinə mükəmməl shuffle permutasiyası tətbiq olunur. $j$ nömrəli çıxış, növbəti sətirdə $n$ -bitlik ikili təsvirinin bir bit sağa rotasiyası ilə əldə olunan $j^{'}$ j' nömrəli girişə birləşdirilir (giriş-çıxışlar soldan sağa nömrələnir).

• Əgər $n > 2$ n > 2-dirsə, növbəti kommutator sətirlərindən sonuncudan bir əvvəlki sətirə qədər sol və sağ tərəflərdə iki $(n - 1)$ (n-1)-Benes subşəbəkələri qurulur.

• Çıxışlarda invers-shuffle permutasiyası tətbiq edilir və son bir kommutator sətiri əlavə edilir.

Məsələn, yuxarıdakı şəkildə $n = 3$ n = 3 üçün Benes şəbəkəsi göstərilib (kvadratlar kommutatorları göstərir; yuxarı və aşağı sətirdəki kompüterlər şəkildə daxil edilməyib, lakin $0$ -dan $7$ -ə kimi nömrələnib). Şəkildə kommutatorların mümkün vəziyyəti göstərilib. İki xəttin kəsişdiyi kvadratlar kommutatorun yandırıldığını göstərir. Bu vəziyyətdə aşağıdakı $0$ , $1$ , $2$ , $3$ , $4$ , $5$ , $6$ , $7$ nömrəli kompüterlərdən yuxarıdakı $3$ , $7$ , $4$ , $0$ , $2$ , $6$ , $1$ , $5$ kompüterlərinə müvafiq olaraq eyni anda məlumat ötürmək mümkündür.

Sizə cütlər şəklində $(a, b)$ kompüterləri verilib (burada $a$ aşağı sətirdə, $b$ isə yuxarı sətirdə olan kompüterdir), bunları eyni zamanda bir-birinə naqil üzrə ayrılmış yollarla birləşdirməlisiniz. Siz bütün kommutatorların vəziyyətini elə müəyyənləşdirməlisiniz ki, bu mümkün olsun.

Giriş

Hər test halında ilk sətirdə $n$ tam ədədi verilir ( $1 \leq n \leq 13$ 1 \leq n \leq 13); bu, yuxarıda təsvir olunduğu kimi, birləşdiriləcək $2^{n}$ 2^n kompüter cütü olduğunu bildirir. $n = 0$ n = 0 olan sətir girişin sonudur və işlənməməlidir.

Hər $n > 0$ n > 0 sətirindən sonra bir sətirdə $2^{n}$ 2^n tam ədəd verilir. $i$ -ci ədəd ( $0 \leq i < 2^{n}$ 0 \leq i < 2^n) aşağıdakı sətrin $i$ -ci kompüterinin birbaşa ünsiyyət qurmalı olduğu yuxarı sıra kompüterinin nömrəsidir.

Çıxış

Hər test üçün çıxış $2 n - 1$ 2n-1 sətirdən ibarət olmalıdır. Hər sətirdə bir ikilik ədədin simvol zənciri var və onda hər kommutatorun yandırılıb ( $1$ ) və ya söndürülüb ( $0$ ) olmasına uyğun informasiya yazılır.

Girişdə həmişə ən az bir həllin olacağı təmin edilir. Əgər bir neçə həll varsa, leksikoqrafik olaraq ən kiçiyini çap edin. Yəni yuxarı sətrin simvol zənciri leksikoqrafik minimal olmalıdır; bərabərlik olarsa, ikinci sətrin simvol zənciri ən kiçik olmalıdır və s.

Fərqli test nümunələrinin çıxışları bir boş sətirlə ayrılmalıdır.

Nümunələr

Nümunə 1