Đề bài

Valerija làm nhân viên giữ xe tại một nhà hàng sang trọng. Công việc của cô là đón những vị khách quý, nhận chìa khóa và đưa xe của họ vào bãi đỗ gần đó. Khi sự kiện kết thúc, cô bảo đảm mỗi vị khách nhận lại đúng xe và vui vẻ rời đi.

Một buổi tối, ngay sau khi đỗ xong tất cả các xe, Valerija nhận thấy một tính chất thú vị về màu sắc của chúng. Có đúng \(2N\) chiếc xe với \(N\) màu khác nhau, và mỗi màu xuất hiện trên đúng hai chiếc xe. Ta biểu diễn các màu bằng những số nguyên từ \(1\) đến \(N\).

Bãi đỗ gồm một dãy \(M\) chỗ, được đánh số từ \(1\) đến \(M\). Mỗi chỗ chứa nhiều nhất hai xe và chỉ có một lối ra vào. Một xe chỉ có thể vào hoặc ra nếu không bị xe khác chắn lối. Xe gần lối vào hơn được gọi là xe trên, còn xe xa lối vào hơn được gọi là xe dưới. Valerija đã đỗ xe sao cho mỗi chỗ hoặc trống, hoặc đầy hai xe, hoặc chỉ có một xe dưới.

Valerija muốn sắp xếp lại sao cho hai xe cùng màu nằm trong cùng một chỗ đỗ. Cô không quan tâm chỗ nào chứa màu nào, cũng không quan tâm xe cụ thể nào nằm trên hay dưới. Việc sắp xếp lại gồm một chuỗi lượt di chuyển.

Trong mỗi lượt, Valerija ngồi vào một chiếc xe đang có thể rời khỏi chỗ hiện tại và lái nó đến một chỗ khác thuộc một trong hai loại sau:

• Chỗ đó đang trống; khi ấy cô đỗ xe làm xe dưới.
• Chỗ đó chỉ chứa một xe cùng màu với chiếc cô đang lái; khi ấy cô đỗ xe làm xe trên.

Valerija muốn dùng ít lượt di chuyển nhất để đạt cách sắp xếp mong muốn. Hãy tìm một chuỗi di chuyển ngắn nhất, hoặc xác định rằng không tồn tại chuỗi nào như vậy.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), cách nhau bởi dấu cách.

Dòng thứ \(i\) trong \(M\) dòng tiếp theo chứa hai số nguyên \(b_i\) và \(t_i\) \((0\le b_i,t_i\le N)\), mô tả chỗ đỗ thứ \(i\). Giá trị \(b_i\) là màu của xe dưới và \(t_i\) là màu của xe trên. Nếu một vị trí trong chỗ đỗ đang trống, số tương ứng bằng \(0\).

Dữ liệu bảo đảm không có chỗ nào chỉ chứa xe trên: nếu \(b_i=0\) thì \(t_i=0\).

Dữ liệu ra

Nếu không tồn tại chuỗi di chuyển nào có thể sắp xếp các xe theo yêu cầu, in -1 trên dòng duy nhất.

Ngược lại, dòng đầu tiên chứa số nguyên \(K\), là số lượt di chuyển nhỏ nhất cần thiết.

Dòng thứ \(i\) trong \(K\) dòng tiếp theo mô tả lượt di chuyển thứ \(i\) và chứa hai số nguyên \(x_i\) và \(y_i\) \((1\le x_i,y_i\le M, x_i\ne y_i)\). Trong lượt đó, Valerija chuyển một xe từ chỗ \(x_i\) sang chỗ \(y_i\).

Tại thời điểm thực hiện lượt di chuyển, chỗ \(x_i\) phải chứa ít nhất một xe. Chiếc xe gần lối vào nhất tại chỗ \(x_i\) phải có thể chuyển đến chỗ \(y_i\): chỗ \(y_i\) phải đang trống hoặc chỉ chứa một xe cùng màu.

Ràng buộc

Trong tất cả các subtask, \(1\le N\le M\le 200\,000\).

Phân nhóm

Nếu lời giải xác định đúng số lượt di chuyển nhỏ nhất cho mọi bộ kiểm thử của một subtask, nhưng mô tả sai một số lượt di chuyển hoặc không in mô tả, lời giải nhận \(20\%\) số điểm của subtask đó.

• Subtask 1 (10 điểm): \(M\le 4\).
• Subtask 2 (10 điểm): \(2N\le M\).
• Subtask 3 (25 điểm): Ban đầu mọi chỗ đỗ đều trống hoặc đầy, và \(N\le 1\,000\).
• Subtask 4 (15 điểm): Ban đầu mọi chỗ đỗ đều trống hoặc đầy.
• Subtask 5 (25 điểm): \(N\le 1\,000\).
• Subtask 6 (15 điểm): Không có ràng buộc bổ sung.

Ví dụ

4 5
1 0
2 0
1 3
4 4
3 2

3
5 2
3 5
3 1

4 5
0 0
2 1
3 1
3 4
2 4

-1

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

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