#include <stdio.h>
#define SIZE 100

int stack[ SIZE ],
    level,
    n,
    m;

int init() {

    stack[level] = 0;
};

void print() {

     int i;

     printf("x      | ");
     for(i = 1; i <= n; i++) printf("%d ",i);
     printf("\n---------------\n");
     printf("f(x)   | ");
     for(i = 1; i <= n; i++) printf("%d ", stack[i]);

     printf("\n\n");
};

int succ() {

   if(stack[level] < m) {

      stack[level]++;

      return 1; 
   }
   return 0;
};

int surjective() {

    int i,j,flag;

    for(i = 1; i <= m; i++) {

        for(j = 1, flag = 0; j <= n && !flag; j++) {

                if(stack[j] == i) flag = 1;
        }  

        if(!flag) return 0;         
    }  
    return 1; 
};

int valid() {

    if(level == n) {

       if(!surjective()) return 0;
    } 

    return 1; 
};

int sol() {

    return level == n;
};

void bt() {

     int hs, is;

     level = 1;

     init();

     while(level > 0) {

           hs = 1; is = 0;

           while(hs && !is) {

                 hs = succ();

                 if(hs) is = valid();
           }

           if(hs) {

             if(sol()) print();

                else {level++;init();}

           } else level--; 
     }  
};

void printSet(int n){

     int it;
     printf("\n{");
     for(it = 1; it <= n; it++) {
         printf("%d ",it);
     }
     printf("}\n");
};

int main() {
    
 //   freopen("Generating.All.Surjective.Functions.out", "w",stdout);
 
    printf("%s\n","Generating All The Surjective Functions:\n");
    
    //f : A -> B
    //A = {1,2,3}, B = {1,2} {(1,1,2),{1,2,1},(1,2,2),{2,1,1},(2,1,2)}

    printf("Domain -> card(A) ");
    scanf("%d",&n);
    printSet(n);
    printf("CoDomain -> card(B) ");
    scanf("%d",&m);
    printSet(m);
    printf("\n");
    bt();    

return(0);
};

I2luY2x1ZGUgPHN0ZGlvLmg+CiNkZWZpbmUgU0laRSAxMDAKCmludCBzdGFja1sgU0laRSBdLAogICAgbGV2ZWwsCiAgICBuLAogICAgbTsKCmludCBpbml0KCkgewoKICAgIHN0YWNrW2xldmVsXSA9IDA7Cn07Cgp2b2lkIHByaW50KCkgewoKICAgICBpbnQgaTsKCiAgICAgcHJpbnRmKCJ4ICAgICAgfCAiKTsKICAgICBmb3IoaSA9IDE7IGkgPD0gbjsgaSsrKSBwcmludGYoIiVkICIsaSk7CiAgICAgcHJpbnRmKCJcbi0tLS0tLS0tLS0tLS0tLVxuIik7CiAgICAgcHJpbnRmKCJmKHgpICAgfCAiKTsKICAgICBmb3IoaSA9IDE7IGkgPD0gbjsgaSsrKSBwcmludGYoIiVkICIsIHN0YWNrW2ldKTsKCiAgICAgcHJpbnRmKCJcblxuIik7Cn07CgppbnQgc3VjYygpIHsKCiAgIGlmKHN0YWNrW2xldmVsXSA8IG0pIHsKCiAgICAgIHN0YWNrW2xldmVsXSsrOwoKICAgICAgcmV0dXJuIDE7IAogICB9CiAgIHJldHVybiAwOwp9OwoKaW50IHN1cmplY3RpdmUoKSB7CgogICAgaW50IGksaixmbGFnOwoKICAgIGZvcihpID0gMTsgaSA8PSBtOyBpKyspIHsKCiAgICAgICAgZm9yKGogPSAxLCBmbGFnID0gMDsgaiA8PSBuICYmICFmbGFnOyBqKyspIHsKCiAgICAgICAgICAgICAgICBpZihzdGFja1tqXSA9PSBpKSBmbGFnID0gMTsKICAgICAgICB9ICAKCiAgICAgICAgaWYoIWZsYWcpIHJldHVybiAwOyAgICAgICAgIAogICAgfSAgCiAgICByZXR1cm4gMTsgCn07CgppbnQgdmFsaWQoKSB7CgogICAgaWYobGV2ZWwgPT0gbikgewoKICAgICAgIGlmKCFzdXJqZWN0aXZlKCkpIHJldHVybiAwOwogICAgfSAKCiAgICByZXR1cm4gMTsgCn07CgppbnQgc29sKCkgewoKICAgIHJldHVybiBsZXZlbCA9PSBuOwp9OwoKdm9pZCBidCgpIHsKCiAgICAgaW50IGhzLCBpczsKCiAgICAgbGV2ZWwgPSAxOwoKICAgICBpbml0KCk7CgogICAgIHdoaWxlKGxldmVsID4gMCkgewoKICAgICAgICAgICBocyA9IDE7IGlzID0gMDsKCiAgICAgICAgICAgd2hpbGUoaHMgJiYgIWlzKSB7CgogICAgICAgICAgICAgICAgIGhzID0gc3VjYygpOwoKICAgICAgICAgICAgICAgICBpZihocykgaXMgPSB2YWxpZCgpOwogICAgICAgICAgIH0KCiAgICAgICAgICAgaWYoaHMpIHsKCiAgICAgICAgICAgICBpZihzb2woKSkgcHJpbnQoKTsKCiAgICAgICAgICAgICAgICBlbHNlIHtsZXZlbCsrO2luaXQoKTt9CgogICAgICAgICAgIH0gZWxzZSBsZXZlbC0tOyAKICAgICB9ICAKfTsKCnZvaWQgcHJpbnRTZXQoaW50IG4pewoKICAgICBpbnQgaXQ7CiAgICAgcHJpbnRmKCJcbnsiKTsKICAgICBmb3IoaXQgPSAxOyBpdCA8PSBuOyBpdCsrKSB7CiAgICAgICAgIHByaW50ZigiJWQgIixpdCk7CiAgICAgfQogICAgIHByaW50ZigifVxuIik7Cn07CgppbnQgbWFpbigpIHsKICAgIAogLy8gICBmcmVvcGVuKCJHZW5lcmF0aW5nLkFsbC5TdXJqZWN0aXZlLkZ1bmN0aW9ucy5vdXQiLCAidyIsc3Rkb3V0KTsKIAogICAgcHJpbnRmKCIlc1xuIiwiR2VuZXJhdGluZyBBbGwgVGhlIFN1cmplY3RpdmUgRnVuY3Rpb25zOlxuIik7CiAgICAKICAgIC8vZiA6IEEgLT4gQgogICAgLy9BID0gezEsMiwzfSwgQiA9IHsxLDJ9IHsoMSwxLDIpLHsxLDIsMX0sKDEsMiwyKSx7MiwxLDF9LCgyLDEsMil9CgogICAgcHJpbnRmKCJEb21haW4gLT4gY2FyZChBKSAiKTsKICAgIHNjYW5mKCIlZCIsJm4pOwogICAgcHJpbnRTZXQobik7CiAgICBwcmludGYoIkNvRG9tYWluIC0+IGNhcmQoQikgIik7CiAgICBzY2FuZigiJWQiLCZtKTsKICAgIHByaW50U2V0KG0pOwogICAgcHJpbnRmKCJcbiIpOwogICAgYnQoKTsgICAgCgpyZXR1cm4oMCk7Cn07

MyAy

3 2