POINTS2 - Điểm và đoạn thẳng
Giới hạn- Thời gian: 0.4s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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
- Người up: paulmcvn