Tower of Hanoi

1#include<bits/stdc++.h>
2using namespace std;
3#define int long long
4vector<pair<int,int>>v;
5void dfs(int k,int i,int j){
6  if(!k) return;
7  dfs(k-1,i,6-i-j);
8  v.emplace_back(i,j);
9  dfs(k-1,6-i-j,j);
10}
11signed main(){
12  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
13  int n; cin>>n;
14  dfs(n,1,3);
15  cout<<v.size()<<'\n';
16  for(auto&p:v) cout<<p.first<<" "<<p.second<<'\n';
17  return 0;
18}