Danut a crescut intr-o metropola numita Bucuresti. Cand a ajuns in clasa a 7-a a realizat ca Bucuresti-ul este un oras foarte ciudat: are 2^N intersectii, fiecare intersectie fiind numerotata cu un numar unic intre 0 si 2^N-1 (inclusiv). Mai mult, se pare ca fostii primari au fost informaticieni la viata lor, pentru ca au construit strazi numai intre doua intersectii pentru care, scrise in baza 2, numerele asociate difera doar printr-o singura cifra. De exemplu intre intersectiile 2 (10) si 3 (11), sau 5 (0101) si 13 (1101) exista strada, dar intre intersectiile 4 (0100) si 9 (1001) sau 11 (01011) si 17 (10001) nu exista strada ce le conecteaza direct.

In plus, strazile au fost si ele numerotate. Astfel, daca intre intersectiile X si Y exista strada atunci ea va fi numerotata cu log₂|X-Y|. Atentie! fiecare strada va fi mereu numerotata cu un numar intreg, si pot exista mai multe strazi numerotate la fel. De exemplu strada ce conecteaza intersectiile 5 si 13 va fi numerotata cu 3 (log₂|5-13| = log₂8 = 3).

Pentru ca nu poate sa adoarma Danut se gandeste in fiecare seara la cate doua intersectii si vrea sa stie toate drumurile disjuncte ce le interconecteaza. Ajutati-l, va rog, sa scape de insomnii.

Cerinta

Dandu-se M perechi de intersectii, determinati pentru fiecare pereche toate drumurile disjuncte intre cele doua intersectii.

Date de intrare

Fisierul de intrare metro.in va contine:

• Pe prima line: N, cu semnificatia ca 2^N reprezinta numarul de intersectii
• Pe a doua linie: M, reprezentand numarul de perechi de intersectii
• Pe liniile 3..M+2: cate doua numere intregi A_i, B_i reprezentand intersectiile pentru care se vor determina drumurile disjuncte ce le intercontecteaza (1 ≤ i ≤ M)

Date de iesire

Fisierul de iesire metro.out va contine pentru fiecare pereche A_i, B_i din fisierul de intrare un numar K_i reprezentand numarul de drumuri disjuncte dintre intersectiile A_i, B_i, iar pe urmatoarele K_i linii se va afisa cate un drum de la A_i la B_i. Pentru fiecare drum se vor afisa numerele strazilor parcurse plecand din intersectia A_i si terminand in intersectia B_i. Numerele strazilor ce apartin aceluiasi drum vor fi despartite prin cate un spatiu.

Restrictii si precizari

• 1 ≤ N, M ≤ 60
• Doua drumuri sunt disjuncte daca au in comun doar prima si ultima intersectie
• Nu exista doua intersectii numerotate la fel
• 0 ≤ A_i, B_i < 2^N
• A_i si B_i sunt distincte
• 1 este putere a lui 2
• Toate drumurile din solutie trebuie sa contina mai putin de 100 de strazi
• Fiecare strada trebuie numerotata cu un numar intre 0 si N-1
• Strazile sunt bidirectionale

Exemplu