Problem: There was no problem about a cactus at the NERC 2020 online round. That's a bad mistake, so judges decided to fix it. You shall not pass to the World Finals 2021 without solving a problem about a cactus!

A cactus is a connected undirected graph in which every edge lies on at most one simple cycle. Intuitively, a cactus is a generalization of a tree where some cycles are allowed. Multiedges (multiple edges between a pair of vertices) and loops (edges that connect a vertex to itself) are not allowed in a cactus. 

Cher has got a cactus. She calls cactus strong if it is impossible to add an edge to it in such a way that it still remains a cactus. But Cher thinks her cactus is not strong enough. She wants to add the smallest possible number of edges to it to make it strong, i. e. to create a new cactus with the same vertices, so that the original cactus is a subgraph of the new one, and it is impossible to add another edge to it so that the graph remains a cactus. Cher hired you to do this job for her. So... it's on you!

Input

The input consists of one or more independent test cases.

The first line of each test case contains two integers n and m (1 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^5), where n is the number of vertices in the graph. Vertices are numbered from 1 to n. Edges of the graph are represented by a set of edge-distinct paths, where m is the number of such paths. 

Each of the following m lines contains a path in the graph. A path starts with an integer number s_i (2 ≤ s_i ≤ 1000) followed by s_i integers from 1 to n. These s_i integers represent vertices of a path. Adjacent vertices in a path are distinct. The path can go through the same vertex multiple times, but every edge is traversed exactly once in the whole test case. There are no multiedges in the graph (there is at most one edge between any two vertices).

The last line of the input after all test cases always contains two zeros. It does not define a test case. It just marks the end of the input and does not require any output.

All graphs in the input are cacti. The total sum of all values of n and the total sum of all values of m throughout the input both do not exceed 10^5.

Output

For each test case, first output the line with the minimal possible number of additional edges A. Then output A lines, each describing one edge as u_i v_i, where u_i and v_i are the numbers of vertices to connect. After adding these edges, the resulting graph must be a strong cactus.

Example

Input


6 1
7 1 2 5 6 2 3 4
3 1
4 1 2 3 1
5 2
3 1 3 5
3 1 2 4
7 2
6 1 2 3 4 5 3
3 6 5 7
0 0


Output


1
1 4
0
1
5 4
2
1 3
6 7

Solution (in CPP):

Solution:
#pragma optimize("SEX_ON_THE_BEACH")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("unroll-all-loops")
#pragma GCC optimize("O3")
 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("fast-math")
#define _FORTIFY_SOURCE 0 
#pragma GCC optimize("no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native") 
 
#include<bits/stdc++.h>
 
using ll = long long int;
using ull = unsigned long long int;
using dd = double;
using ldd = long double;
 
namespace someUsefull {
    template<typename T1, typename T2>
    inline void checkMin(T1& a, T2 b) {
        if (a > b)
            a = b;
    }
 
    template<typename T1, typename T2>
    inline void checkMax(T1& a, T2 b) {
        if (a < b)
            a = b;
    }
 
    const int _bitfunctions_size_ = 16;
    const int _bitfunctions_mask_ = (1 << _bitfunctions_size_) - 1;
    char* _bits_count_;
    
    inline void _build_bits_count_() {
        _bits_count_ = new char[1 << _bitfunctions_size_];
        for (int i = 1; i < (1 << _bitfunctions_size_); ++i) {
            _bits_count_[i] = _bits_count_[i >> 1];
            if (i & 1) ++_bits_count_[i];
        }
    }
 
    template<typename T1 = char, typename T2 = int>
    inline T1 popcnt(T2 x) {
        T1 ans = 0;
        while (x) {
            ans += _bits_count_[x & _bitfunctions_mask_];
            x >>= _bitfunctions_size_;
        }
        return ans;
    }
}
 
namespace operators {
    template<typename T1, typename T2>
    std::istream& operator>>(std::istream& in, std::pair<T1, T2>& x) {
        in >> x.first >> x.second;
        return in;
    }
 
    template<typename T1, typename T2>
    std::ostream& operator<<(std::ostream& out, std::pair<T1, T2> x) {
        out << x.first << " " << x.second;
        return out;
    }
 
    template<typename T1>
    std::istream& operator>>(std::istream& in, std::vector<T1>& x) {
        for (auto& i : x) in >> i;
        return in;
    }
 
    template<typename T1>
    std::ostream& operator<<(std::ostream& out, std::vector<T1>& x) {
        for (auto& i : x) out << i << " ";
        return out;
    }
}
 
//name spaces
using namespace std;
using namespace operators;
using namespace someUsefull;
//end of name spaces
 
//defines
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()


//end of defines
//#undef HOME
//debug defines
#ifdef HOME
    #define debug(x) cerr << #x << " " << x << endl;
    #define debug_v(x) {cerr << #x << " "; for (auto ioi : x) cerr << ioi << " "; cerr << endl;}
    #define debug_vp(x) {cerr << #x << " "; for (auto ioi : x) cerr << '[' << ioi.ff << " " << ioi.ss << ']'; cerr << endl;}
    #define debug_v_v(x) {cerr << #x << "/*\n"; for (auto ioi : x) { for (auto ioi2 : ioi) cerr << ioi2 << " "; cerr << '\n';} cerr << "*/" << #x << endl;}
    int jjj;
    #define wait() cin >> jjj;
    #define PO cerr << "POMELO" << endl;
    #define OL cerr << "OLIVA" << endl;
    #define gen_clock(x) cerr << "Clock " << #x << " created" << endl; ll x = clock(); 
    #define check_clock(x) cerr << "Time spent in " << #x << ": " << clock() - x << endl; x = clock();
    #define reset_clock(x) x = clock();
    #define say(x) cerr << x << endl;
#else
    #define debug(x) 0;
    #define debug_v(x) 0;
    #define debug_vp(x) 0;
    #define debug_v_v(x) 0;
    #define wait() 0;
    #define PO 0;
    #define OL 0;
    #define gen_clock(x) 0;
    #define check_clock(x) 0;
    #define reset_clock(x) 0;
    #define say(x) 0;
#endif // HOME

vector<set<int>> gr;
vector<int> tin;
vector<int> tout;
vector<bool> was;
vector<pair<int, int>> br;

int t = 0;
void findBr(int v, int p = -1) {
	was[v] = 1;
	tin[v] = tout[v] = t++;
	for (int to : gr[v]) {
		if (to == p) continue;
		if (was[to]) checkMin(tout[v], tin[to]);
		else {
			findBr(to, v);
			checkMin(tout[v], tout[to]);
			if (tout[to] > tin[v]) {
				br.push_back({v, to});
			}
		}
	}
}

vector<int> cmp;
vector<pair<int, int>> edges;

void calcC(int v, int p = -1) {
	cmp.push_back(v);
	for (int to : gr[v]) {
		if (to == p) continue;
		if (gr[v].size() % 2 && gr[to].size() % 2) edges.push_back({v, to});
		calcC(to, v);
	}
}

vector<set<int>> nchg;

void buildnch() {
	for (auto i : edges) {
		nchg[i.ff].insert(i.ss);
		nchg[i.ss].insert(i.ff);
	}
}

void debuildnch() {
	for (int i : cmp) nchg[i].clear();
}

vector<pair<int, int>> dp; // can't can

void bdp(int v, int p = -1) {
	was[v] = 1;
	int cp = 0;
	for (int to: nchg[v]) {
		if (to == p) continue;
		bdp(to, v);
		cp += dp[to].ff;
	}
	dp[v] = {cp, cp};
	for (int to : nchg[v]) {
		if (to == p) continue;
		cp -= dp[to].ff;
		checkMax(dp[v].ff, 1 + cp + dp[to].ss);
		cp += dp[to].ff;
	}
	checkMax(dp[v].ff, dp[v].ss);
}

vector<pair<int, int>> dpRearmed;

void rearm(int v, bool can = 1, int p = -1) {
	was[v] = 1;
	if (can == 0 || dp[v].ss >= dp[v].ff) {
		for (int to : nchg[v]) if (to != p) rearm(to, 1, v);
		return;
	}
	int cp = 0;
	for (int to: nchg[v]) {
		if (to == p) continue;
		cp += dp[to].ff;
	}
	int too = -1;
	for (int to : nchg[v]) {
		if (to == p) continue;
		cp -= dp[to].ff;
		if (dp[v].ff == 1 + cp + dp[to].ss) {
			dpRearmed.push_back({v, to});
			too = to;
			break;
		}
		cp += dp[to].ff;
	}
	for (int to : nchg[v]) {
		if (to == p) continue;
		if (to == too) rearm(to, 0, v);
		else rearm(to, 1, v);
	}
}

vector<pair<int, int>> ans;

pair<int, int> eulC(int v, int p = -1, int d = 0) {
	was[v] = 1;
	vector<pair<int, int>> pr;
	for (int to : gr[v]) {
		if (to == p) continue;
		pair<int, int> x = eulC(to, v, d + 1);
		if (x.ff != -1) {
			pr.push_back(x);
		}
	}
	sort(all(pr));
	if (gr[v].size() % 2) {
		debug_v(pr);
		if (pr.size() && pr.back().ff == d + 1) {
			while (pr.size()) {
				int x = pr.back().ss;
				pr.pop_back();
				int y = pr.back().ss;
				pr.pop_back();
				ans.push_back({x, y});
			}
			return {d, v};
		}
		pr.push_back({d, v});
	}
	while (pr.size() > 1) {
		int x = pr.back().ss;
		pr.pop_back();
		int y = pr.back().ss;
		pr.pop_back();
		ans.push_back({x, y});
	}
	if (pr.size() % 2 == 0) return {-1, -1};
	return pr.back();
}

void solve(int test) {
    //cout << "Case #" << test << ": ";

	int n, m;
	cin >> n >> m;
	if (n == 0) exit(0);
	gr.clear();
	gr.resize(n);
	for (int i = 0; i < m; ++i) {
		int s;
		cin >> s;
		vector<int> arr(s);
		cin >> arr;
		for (int i = 0; i < s - 1; ++i) {
			gr[arr[i] - 1].insert(arr[i + 1] - 1);
			gr[arr[i + 1] - 1].insert(arr[i] - 1);
		}
	}
	PO;
	tin.clear();
	tin.resize(n);
	tout.clear();
	tout.resize(n);
	was.clear();
	was.resize(n);
	br.clear();
	nchg.clear();
	nchg.resize(n);
	dp.clear();
	dp.resize(n);
	ans.clear();
	findBr(0);
	PO;
	debug_v(br);

	for (int i = 0; i < n; ++i) gr[i].clear();

	for (auto i : br) {
		gr[i.ff].insert(i.ss);
		gr[i.ss].insert(i.ff);
	}
	PO;

	was.assign(n, 0);

	for (int i = 0; i < n; ++i) {
		if (was[i]) continue;
		cmp.clear();
		edges.clear();
		calcC(i);
		debug_v(edges);
		buildnch();
		
		for (int j : cmp) {
			if (!was[j]) {
				bdp(j);
			}
		}
		debug_v(dp);
		dpRearmed.clear();
		for (int j : cmp) was[j] = 0;
		for (int j : cmp) {
			if (!was[j]) {
				rearm(j);
			}
		}
		debug_v(dpRearmed);
		
		for (auto i : dpRearmed) {
			gr[i.ff].erase(i.ss);
			gr[i.ss].erase(i.ff);
		}
		for (int v : cmp) was[v] = 0;
		for (int v : cmp) {
			if (was[v]) continue;
			debug(v);
			eulC(v);
		}

		debuildnch();
	}

	cout << ans.size() << '\n';
	for (auto i : ans) cout << i.ff + 1 << " " << i.ss + 1 << '\n';
		cout << endl;

}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    _build_bits_count_();

    #ifdef HOME
    //freopen("input.txt", "r", stdin);
    #endif // HOME

    int t = 1;
    //cin >> t;
 
    for (int i = 0; i >= 0; ++i) {
        solve(i + 1);
    }
    return 0;
}

/*
3 
6 2
1 1 2 2 3
6 6
1 1 2 2 3
6 4
1 2 3 4 5
*/