#include #include #define chmin(x,y) (x) = min((x),(y)) #define chmax(x,y) (x) = max((x),(y))z using namespace std; using namespace atcoder; using ll = long long; const ll mod = 998244353; using mint = modint998244353; using Graph = vector>>; const vector dx = {1,0,-1,0}, dy = {0,1,0,-1}; double dist(int x1, int y1, int x2, int y2){ double res = (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2); return sqrt(res); } ll need(ll n, ll m){ ll res = 0; if(n < 0) return res; res = n / m; if(n % m > 0) res++; return res; } ll d2(ll x1, ll y1, ll x2, ll y2){ // auto [x1,y1] = p; // auto [x2,y2] = q; ll res = (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2); return res; } int main(){ // input ll X; cin >> X; // prep: prime_factorization <= 2e5 vector> pf; for(ll i = 2; i * i <= X && i <= 200000; i++){ if(X % i != 0) continue; int ex = 0; while(X % i == 0){ X /= i; ex++; } pf.emplace_back(i,ex); } if(X != 1 || pf.empty()) pf.emplace_back(X,1); // solve ll green = 0, brown = 0; vector bs; for(auto p : pf){ if(p.first == 2){ green += 4 * (p.second / 2) + 2 * (p.second % 2); brown += p.second / 2 + p.second % 2; for(int i = 0; i < p.second / 2; i++) bs.push_back(4); if(p.second % 2 == 1) bs.push_back(2); } else{ green += p.first * p.second; brown += p.second; for(int i = 0; i < p.second; i++) bs.push_back(p.first); } } // output if(brown + green > 200000) cout << -1 << endl; else{ // output # of vertices cout << brown + green << endl; // output edges between brown vertices for(int i = 1; i < bs.size(); i++) cout << i << " " << i+1 << endl; // output edges between brown vertex and green vertex int green_id = bs.size() + 1; for(int i = 0; i < bs.size(); i++){ for(int j = 0; j < bs[i]; j++){ cout << i+1 << " " << green_id << endl; green_id++; } } // output vertices' color for(int i = 0; i < brown; i++){ if(i) cout << " b"; else cout << "b"; } for(int i = 0; i < green; i++){ cout << " g"; } cout << endl; } }