Đây là một bài toán tương tác

Thi đấu với máy tính trong các trò chơi đối kháng luôn tạo ra nhiều cảm hứng cho người chơi. Lần này Hùng gặp phải một trò chơi hóc búa với máy tính sau đây.

Trò chơi diễn ra trên một đa giác lồi ~n~ đỉnh được đánh số từ ~1~ đến ~n~ theo chiều kim đồng hồ, trong đó người ta đã vẽ ~m~ đường chéo sao cho không có hai đường chéo nào cắt nhau ở trong đa giác và không có ~3~ đỉnh nào đôi một có đoạn nối (có thể là cạnh hoặc đường chéo của đa giác).

Hai đấu thủ luân phiên thực hiện nước đi. Đến lượt mình, người chơi phải vẽ thêm một đường chéo của đa giác sao cho đường chéo này không cắt bất cứ đường chéo nào đã vẽ trước đó tại điểm nằm trong đa giác và đồng thời không có bất cứ tam giác nào được tạo ra (nghĩa là không xuất hiện ~3~ đỉnh nào của đa giác đôi một có đoạn nối). Người đến lượt mà không có cách thực hiện được lượt đi là người thua cuộc và tất nhiên, đối thủ của anh ta là người giành phần thắng.

Hùng được quyền lựa chọn là người thực hiện nước đi trước hay sau, hãy giúp Hùng lựa chọn quyền thực hiện nước đi trước hay sau và thực hiện các lượt chơi để giành phần thắng.

Input

Dòng đầu tiên gồm hai số nguyên ~n, m~ (~n\le 100000~) — số đỉnh và số đường chéo đã nối sẵn của đa giác.

Mỗi dòng trong ~m~ dòng tiếp theo gồm hai số nguyên ~u,v~ thể hiện một đường chéo đã nối sẵn.

Interaction

Nếu bạn muốn Hùng đi trước, in ra "~0\ 0~".

Khi đến lượt của Hùng, nếu muốn nối đường chéo ~u-v~, in ra "~u\ v~".

Khi đến lượt của máy, đọc vào nước đi của máy dưới dạng "~x\ y~", máy sẽ nối đường chéo ~x-y~.

Nếu bạn thực hiện một nước đi không hợp lệ hoặc máy tính không thể thực hiện nước đi, chương trình sẽ dừng ngay lập tức.

Sau khi in ra một nước đi, đừng quên xuống dòng và flush đầu ra chuẩn, nếu không bạn có thể nhận verdict Time limit exceedded. Để làm điều này, bạn có thể sử dụng:

• fflush(stdout) hoặc cout.flush() trong C++;

• System.out.flush() trong Java;

• flush(output) trong Pascal;

• stdout.flush() trong Python;

• xem tài liệu chuẩn đối với các ngôn ngữ khác.

Scoring

Sample Input 1

10 1
1 8

2 5

Sample Output 1

0 0

5 8