Cho một đơn đồ thị vô hướng \(n\) đỉnh \((2 \leq n \leq {10}^5)\), \(m\) cạnh, đồ thị không có khuyên và cạnh song song. Ta có thể thực hiện phép "hợp" hai đỉnh \(u\) và \(v\) (không có cạnh nối trực tiếp) lại như sau:

• Thêm một đỉnh \(x\) vào đồ thị.
• Nối các cạnh \((x, w)\) trong đó \(w\) là đỉnh có cạnh nối tới u hoặc v.
• Xóa đỉnh \(u\) và \(v\) ra khỏi đồ thị.

Yêu cầu: Hãy thực hiện một số thao tác "hợp" như trên để biến đồ thị ban đầu thành một "đường thẳng". Nếu có nhiều cách thực hiện thì hãy đưa ra một cách bất kì.

Một đồ thị được gọi là đồ thị "đường thẳng" khi và chỉ khi thỏa mãn hai điều kiện sau

• đồ thị liên thông,
• có đúng hai đỉnh có bậc là \(1\), và \(n-2\) đỉnh còn lại có bậc là \(2\).

Đồ thị "đường thẳng" có dạng như sau:

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n, m ~ \left(1 \leq m \leq \min\left({10^5}, \frac{n(n-1)}{2} \right) \right)\).
• \(m\) dòng tiếp theo, dòng thứ \(i ~ (1 \leq i \leq m)\) chứa hai số nguyên dương \(u_i, v_i ~ (1 \leq u_i, v_i \leq n, u_i \neq v_i)\) biểu diễn một cạnh nối của đồ thị, tức là cạnh thứ \(i\) nối hai đỉnh \(u_i\) và \(v_i\).

Output

Nếu không thể làm đồ thị đã cho trở thành một "đường thẳng" thì đưa ra duy nhất một số nguyên \(-1\).

Nếu có thể thì hãy đưa ra đáp án của bạn theo định dạng sau:

• Dòng đầu tiên chứa một số nguyên không âm \(q ~ (0 \leq q \leq n - 1)\) là số phép "hợp" bạn sử dụng.
• \(q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u_i, v_i ~ (1 \leq u_i, v_i < n + i)\) thể hiện rằng tại lần sử dụng phép "hợp" thứ \(i ~ (1 \leq i \leq q)\), hai đỉnh \(u_i\) và \(v_i\) được hợp lại thành đỉnh \(x_i = n + i\).

Scoring

• Subtask 1 (\(10\%\) số điểm): \(n \leq 10\).
• Subtask 2 (\(30\%\) số điểm): \(n \leq 20\).
• Subtask 3 (\(30\%\) số điểm): \(n \leq 3000\).
• Subtask 4 (\(30\%\) số điểm): \(n \leq {10}^5\).

Example

2 1
1 2

0

4 4
1 2
2 3
3 4
4 1

1
1 3

3 3
1 2
2 3
1 3

-1