//----------------------------------------------------------------------------------------
// Euler cycle algorithm to construct a k-ary de Bruijn sequence

// PROGRAMMED BY: Joe Sawada -- 2018, udpdated for debruijnsequence.org 2020
//----------------------------------------------------------------------------------------
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define MAX_k 10
#define MAX_n 30

int n,k,a[MAX_n];
char *visited;
long long int (*G)[MAX_k];
long long int (*G2)[MAX_k];
int total=0;

//===============================================================
// Convert the binary string to an integer
//===============================================================
long int GetNum(int start) {
    long long int sum=0;
    int i;
    
    //Convert substring of length n-1 (starting from start)
    for (i=start; i<start+(n-1); i++)  sum += pow(k,i-start) * a[i];

    return sum;
}
//===============================================================
// Add the k edges from the vertex a[1..n-1], mapped to integers
//===============================================================
void AddEdges() {
    long long int u,v;
    int i;
    
    u = GetNum(1);
    for (i=0; i<k; i++) {
        a[n] = i;
        v = GetNum(2);
        G[u][i] = v;
        
        a[0] = i;
        v = GetNum(0);
        G2[u][i] = v;
    }
}
//=========================================================================
// Recursively generate vertices of DB graph (binary strings of length n-1)
//=========================================================================
void GenVertices(int t) {
    int i;
    
    if (t > n-1) AddEdges();
    else {
        for (i=0; i<k; i++) {
            a[t] = i;
            GenVertices(t+1);
        }
    }
}
//=========================================================================
// Set the edge (u,v) to end of adjacency list
//=========================================================================
void SetExtreme(long long int u, long long int v) {
    int i;

    for (i=0; i<k-1; i++) {
        if (G[u][i] == v) {
            G[u][i] = G[u][k-1];
            G[u][k-1] = v;
        }
    }
}
//=========================================================================
// DFS starting from 0 - FIND A SPANNING OUT TREE AND USE TO SET ADJ LISTS
// (Recursion not used due to stack depth)
//=========================================================================
void DFS() {
    long long int u,v,t;
    int i,new;
    long long int (*Q);

    Q = malloc(sizeof(long long int) * pow(k,n-1));
    
    t = 0;
    Q[0] = 0;   // Initialize Q to vertex 0000...000
    
    while (t >= 0) {
        v = Q[t];
        visited[v] = 1;
        new = 0;
        for (i=0; i<k; i++) {
            u = G2[v][i];
            if (visited[u] == 0 && new == 0) {
                SetExtreme(u,v);
                Q[++t] = u;
                new = 1;
            }
        }
        if (new == 0) t--;
    }
}
//=========================================================================
// Get next vertex in adjacency list by shifting the list left
//=========================================================================
long int GetNext(long long int v) {
    long long int u;
    int i;
    
    u = G[v][0];
    for (i=0; i<k-1; i++) G[v][i] = G[v][i+1];
    G[v][k-1] = -1;
    
    return u;
}
//=========================================================================
// Generate the DB sequence by visiting an Euler Cycle
//=========================================================================
void DB() {
    long long int u,v;
    
    printf("\n");
    v = 0;
    while (v != -1) {
        u = GetNext(v);
        if (u != -1) printf("%d", (int) u%k);
        v=u;
    }
    printf("\n\n");
}
//=========================================================================
int main() {
    long long int i;
    int len;
    
    printf("Enter n: ");    scanf("%d", &n);
    printf("Enter k: ");    scanf("%d", &k);
    
    if (n == 1) {
        printf("\n");
        for (i=0; i<k; i++) printf("%lld", i);
        printf("\n\n");
        return 1;
    }
    
    len = (int) pow(k,n);
    G =  malloc (len * sizeof(long long int) * MAX_k);
    G2 = malloc (len * sizeof(long long int) * MAX_k);
    visited = (char *) malloc(sizeof(char) * len);
    
    for (i=0; i<len; i++) visited[i] = 0;

    GenVertices(1); // Create the DB graph and its reversal
    DFS();          // Compute spanning in-tree and compute order adj lists
    DB();           // Find Euler Cycle
                 
    free(G); free(G2); free(visited);
}