Giải bài trực tuyến

Theodor và Maxim trong giờ tin học thường hay chơi một trò chơi có tên gọi là "Điểm và đoạn thẳng". Ban đầu có một tờ giấy, trên đó có vẽ n điểm. Hai người sẽ lần lượt chơi.

Trong một lượt, người đi sẽ nối hai điểm mà chưa được nối. Ví dụ, trong hình vẽ dưới đây, ta có thể nối các điểm 1 và 2, 2 và 4, hoặc nối một trong số các điểm 1, 2, 3, 4 với 5 hoặc 6.

Nếu sau một lượt đi mà các điểm trở nên liên thông, nghĩa là từ một điểm bất kỳ có thể đi đến một điểm bất kỳ khác qua các đoạn thẳng đã được nối thì người đi lượt đi này là người thắng cuộc.

Theodor tìm thấy một hộp giấy có vẽ các ván đấu đang bỏ dở. Theodor nghĩ ra một bài toán thú vị là xác định xem ai sẽ giành chiến thắng nếu tiếp tục chơi ván đấu bỏ dở đó nếu Theodor là người đi lượt tiếp theo và hai người chơi đều sử dụng chiến thuật tối ưu. Hãy lập trình giúp Theodor xác định người thắng cuộc trong các ván đấu.

Dữ liệu

Dòng đầu tiên chứa số nguyên T (T ≤ 5) là số lượng bộ test. Mỗi bộ test có dạng như sau:

Dòng đầu tiên chứa số nguyên n - số lượng các điểm và m - số lượng các đoạn thẳng đã được vẽ (2 ≤ n ≤ 150, 0 ≤ m ≤ n(n-1)/2). m dòng sau mỗi dòng chứa hai số nguyên là chỉ số của hai đầu mút của một đoạn thẳng.

Mỗi bộ test cách nhau bởi khoảng trắng.

Kết quả

Với mỗi bộ test, in ra dòng chữ "Theodor" hoặc "Maxim" tùy thuộc vào việc "Theodor" hay "Maxim" dành chiến thắng.

Ví dụ

Dữ liệu
3

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

5 0

2 1
1 2

Kết quả
Theodor
Maxim
Maxim 

Nguồn: Цикл Интернет-олимпиад для школьников, сезон 2008-2009