#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; vi elms[200001]; vi poz[200001]; vi graph[200001]; bool odw[200001]; int up_cnt[200001]; int down_cnt[200001]; int n,m; vector<vi> comps; vi comp; vector<pii> opers; unordered_set<int> zero_ind; void add_oper(int a, int b) { elms[b].pb(elms[a].back()); elms[a].pop_back(); if(siz(elms[a]) == 0) zero_ind.insert(a); if(siz(elms[b]) == 1) zero_ind.erase(b); opers.pb({a+1,b+1}); } void dfs(int v) { odw[v] = 1; comp.pb(v); forall(it,graph[v]) if(!odw[it]) dfs(it); } pii get_val(vi c) { int up_c = 0; bool is_path = 0; forall(it,c) { if(siz(elms[it]) == 1) is_path = 1; if(siz(elms[it]) == 2 && up_cnt[elms[it][1]] == 2) up_c++; } up_c /= 2; if(!is_path) { if(up_c == 0) return {1,-1}; return {up_c >= 2 ? 2 : 1,0}; } return {up_c >= 1 ? 1 : 0,1}; } void solve(vi c) { bool is_path = 0; forall(it,c) if(siz(elms[it]) == 1) is_path = 1; if(!is_path) { int f = *zero_ind.begin(); int d = -1; forall(it,c) if(up_cnt[elms[it][1]] == 2) d = elms[it][1]; if(d != -1) { forall(it,poz[d]) add_oper(it,f); comp = {}; forall(it,c) odw[it] = 0; odw[poz[d][0]] = 1; dfs(poz[d][1]); c = comp; c.pb(poz[d][0]); } else { if(elms[c[0]][1] != elms[c[1]][0]) reverse(all(c)); add_oper(c[0],f); int pop = c[0]; for(int i = siz(c)-1; i >= 1; i--) { add_oper(c[i],pop); pop = c[i]; } add_oper(c[1],f); return; } } int ind = 0; while(ind < siz(c)-1) { if(elms[c[ind]][0] == elms[c[ind+1]][1]) { add_oper(c[ind+1],c[ind]); ind++; continue; } int p = -1; for(int i = ind+1; i < siz(c)-1; i++) { if(up_cnt[elms[c[i]][1]] == 2) { p = i; break; } } if(p != -1) { int f = *zero_ind.begin(); add_oper(c[p],f); add_oper(c[p+1],f); for(int i = p-1; i >= ind; i--) { add_oper(c[i],c[i+1]); } ind = p+1; } else { for(int i = siz(c)-2; i >= ind; i--) { add_oper(c[i],c[i+1]); } return; } } } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); cin >> m >> n; int zero_cnt = 0; rep(i,n) { int a,b; cin >> a >> b; up_cnt[b]++; down_cnt[a]++; if(a == 0) { zero_cnt++; zero_ind.insert(i); } if(a != 0) elms[i].pb(a); if(b != 0) elms[i].pb(b); } rep(i,n) forall(it,elms[i]) if(it != 0) poz[it].pb(i); rep2(i,1,m) { graph[poz[i][0]].pb(poz[i][1]); graph[poz[i][1]].pb(poz[i][0]); } rep(i,n) { if(odw[i]) continue; if(siz(graph[i]) == 1) { comp = {}; dfs(i); comps.pb(comp); } } int ans = m; rep2(i,1,m) if(up_cnt[i] == 2) ans++; rep(i,n) { if(odw[i]) continue; comp = {}; dfs(i); if(siz(comp) != 1) comps.pb(comp); else if(siz(elms[i]) == 2) ans--; } vector<pair<pii,int>> vs; rep(i,siz(comps)) { vs.pb({get_val(comps[i]),i}); } sort(all(vs)); forall(it,vs) { if(zero_cnt < it.ff.ff) { cout << "-1\n"; return 0; } solve(comps[it.ss]); if(it.ff.ss == -1) ans++; else zero_cnt += it.ff.ss; } cout << ans << '\n'; forall(it,opers) cout << it.ff << " " << it.ss << "\n"; }