火车进栈

using namespace std;
int n, cnt = 20;
vector<int>st3;
stack<int>st2;
int st1 = 1;
void dfs()
{
  if(!cnt)return ;
  if(st3.size() == n ) // 1
  {
          cout << "1\n" ; 
      cnt --;
      for(auto x : st3)cout << x;
      cout << endl;
      
  }
  if(st2.size()) // 2
  {
          cout << "2->" ; 
    st3.push_back(st2.top());
    st2.pop();
    dfs();
    
    st2.push(st3.back());
    st3.pop_back();
  }
  if(st1 <= n){ // 3 
  cout << "3->" ; 
    st2.push(st1);
    st1 ++;
    dfs();
    
    st2.pop();//恢复现场是在回溯的时候用的
    st1 --;//在第二步dfs回溯后，会改变父节点的st2和st1
  }

}
int main()
{
  cin >> n;
  dfs();
}