Código - 1671 - URI

#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define endl '\n'

using namespace std;

using ll = long long;
using pii = pair<int, int>;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1000000007;
const int dx[] = { 0, 0, -1, 1, 1, -1,  1, -1};
const int dy[] = {-1, 1,  0, 0, 1, -1, -1,  1};

typedef pair<int, int> pii;
template<bool directed=false> struct EulerianPath{
  vector<vector<pii>> adj;
  vector<int> ans, pos;
  vector<bool> used;
  int n, m;
  EulerianPath(int n1){
    n = n1; m = 0;
    adj.assign(n, vector<pii>());
  }
  void addEdge(int a, int b) {
    int at = m++;
    adj[a].push_back({b, at});
    if (!directed) adj[b].push_back({a, at});
  }
  void dfs(int u){
    stack<int> st;
    st.push(u);
    while(!st.empty()){
      u = st.top();
      if(pos[u] < adj[u].size()){
        auto [to, id] = adj[u][pos[u]];
        pos[u]++;
        if(!used[id]){
          used[id] = true;
          st.push(to);
        }
      }else{
        ans.push_back(u);
        st.pop();
      }
    }
  }
  // Remember to call the correct src
  // If you want to check if there is an answer remember to check if all |components| > 1 of the graph are connected
  vector<int> getPath(int src){
    pos.assign(n, 0);
    used.assign(m, false);
    ans.clear();
    dfs(src);
    reverse(ans.begin(), ans.end());
    return ans;
  }
};
int main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  while(true){
    int n;
    cin >> n;
    if(n == 0)
      break;
    if(n == 1){
      cout << "0123456789" << endl;
      continue;
    }
    int lim = 1;
    for(int i=1; i<=n-1; i++)
      lim *= 10;
    EulerianPath<true> graph(lim);
    for(int i=0; i<lim; i++){
      for(int j=0; j<10; j++){
        int next = (i*10 + j)%lim;
        graph.addEdge(i, next);
      }
    }
    string ans(n-2, '0');
    auto path = graph.getPath(0);
    for(int x: path){
      ans += ('0' + (x%10));
    }
    cout << ans << endl;
  }
  return 0;
}