Điểm và đoạn thẳng

View as PDF

Submit solution

Points: 1.40 (partial)
Time limit: 0.6s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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~.

image

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.

Input

Dòng đầu tiên chứa số nguyên ~T~ ~(T \leq 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 \leq n \leq 150~, ~0 \leq m \leq \frac{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.

Output

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.

Sample Input

3

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

5 0

2 1
1 2

Sample Output

Theodor
Maxim
Maxim

Comments

Please read the guidelines before commenting.


There are no comments at the moment.