Có $N$ giáo viên và $N$ học sinh ở Seoul Science High School. Mỗi học sinh đã mua $N$ bông hoa vì ngày mai là Ngày Nhà giáo ở Hàn Quốc. Tuy nhiên, một học sinh đã thôi học, và hiện trường chỉ còn $N-1$ học sinh.

Các giáo viên rất hay ghen tị, nên họ sẽ cho một học sinh điểm F nếu số hoa nhận được từ học sinh đó ít hơn các giáo viên khác. Vì vậy, mỗi giáo viên phải nhận đúng $N-1$ bông hoa. Một học sinh chỉ có thể tặng hoa cho những giáo viên đã từng dạy mình, và bạn biết những học sinh nào đã học với những giáo viên nào.

Younghun là học sinh của Seoul Science High School và cần bạn giúp tổ chức sự kiện này.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $M$ ($2 \le N \le 100 000$, $1 \le M \le 200 000$), mô tả số giáo viên và số cặp (học sinh, giáo viên) mà học sinh đã học với giáo viên đó.

$M$ dòng tiếp theo mô tả các mối quan hệ: dòng thứ $j$ chứa hai số nguyên $s_j$, $t_j$ ($1 \le s_j \le N-1$, $1 \le t_j \le N$), cho biết học sinh thứ $s_j$ có thể tặng hoa cho giáo viên thứ $t_j$. Đảm bảo rằng tất cả các cặp đều khác nhau.

Dữ liệu ra

Nếu không thể tặng cho tất cả giáo viên cùng số hoa ($N-1$ bông), hãy in một số $-1$ trên dòng đầu.

Ngược lại, chương trình của bạn phải in $M$ dòng. Dòng thứ $j$ phải chứa một số nguyên biểu thị số hoa mà học sinh thứ $s_j$ tặng cho giáo viên thứ $t_j$.

Nếu có nhiều đáp án hợp lệ, bạn có thể in bất kỳ đáp án nào.

Ví dụ

Dữ liệu vào 1

6 12
1 3
1 4
1 5
2 2
2 4
3 1
3 3
4 1
4 2
4 4
5 4
5 6

Dữ liệu ra 1

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

Dữ liệu vào 2

6 12
1 2
1 3
1 4
2 2
2 4
3 1
3 3
4 1
4 2
4 4
5 5
5 6

Dữ liệu ra 2

-1