Ada $N$ guru dan $N$ siswa di Seoul Science High School. Setiap siswa membeli $N$ bunga karena besok adalah Hari Guru di Korea. Namun, salah satu siswa berhenti sekolah, dan sekarang hanya tersisa $N-1$ siswa di sekolah.

Para guru sangat mudah iri, sehingga mereka akan memberikan nilai F kepada seorang siswa jika menerima lebih sedikit bunga dari siswa itu dibandingkan guru lain. Oleh karena itu, setiap guru harus menerima tepat $N-1$ bunga. Seorang siswa hanya boleh memberikan bunga kepada guru yang pernah mengajarnya, dan kamu mengetahui siswa mana yang pernah belajar dari guru mana.

Younghun adalah siswa Seoul Science High School, dan ia membutuhkan bantuanmu untuk mengatur acara ini.

Masukan

Baris pertama berisi dua bilangan bulat $N$ dan $M$ ($2 \le N \le 100 000$, $1 \le M \le 200 000$) yang menyatakan jumlah guru dan jumlah pasangan (siswa, guru) di mana siswa tersebut pernah belajar dari guru tersebut.

$M$ baris berikutnya menjelaskan hubungan: baris ke-$j$ berisi dua bilangan bulat $s_j$, $t_j$ ($1 \le s_j \le N-1$, $1 \le t_j \le N$), yang menunjukkan bahwa siswa ke-$s_j$ dapat memberikan bunga kepada guru ke-$t_j$. Dijamin semua pasangan berbeda.

Keluaran

Jika tidak mungkin memberikan jumlah bunga yang sama ($N-1$ bunga) kepada semua guru, cetak satu bilangan $-1$ pada baris pertama.

Jika tidak, programmu harus mencetak $M$ baris. Pada baris ke-$j$, harus ada satu bilangan bulat yang menyatakan jumlah bunga yang diberikan siswa ke-$s_j$ kepada guru ke-$t_j$.

Jika terdapat beberapa jawaban yang mungkin, kamu boleh mencetak salah satunya.

Contoh

Masukan 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

Keluaran 1

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

Masukan 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

Keluaran 2

-1