Kiên và trò chơi trên đồ thị

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 2.0s
Memory limit: 250M
Input: stdin
Output: stdout

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

Kiên có một đồ thị vô hướng gồm ~N~ đỉnh đánh số từ ~1~ tới ~N~ và ~M~ cạnh đánh số từ ~1~ đến ~M~. Cạnh thứ ~i~ kết nối hai đỉnh ~a_i~ và ~b_i~.

Một đồ thị được gọi là đẹp nếu nó thỏa mãn những điều kiện sau:

  • Không có cạnh nối giữa một đỉnh tới chính nó
  • Có nhiều nhất một cạnh nối giữa hai đỉnh bất kỳ
  • Đỉnh ~1~ và đỉnh ~N~ không liên thông.

Kiên rủ Thế chơi một trò chơi trên đồ thị của mình. Hai người chơi sẽ thay phiên nhau thực hiện nước đi của mình và Kiên là người đi trước.

  • Trong một nước đi, ngưới tới lượt chơi sẽ chọn hai đỉnh ~u~ và ~v~, sau đó thêm cạnh nối hai chiều giữa hai đỉnh này vào đồ thị

Người chơi đầu tiên thực hiện nước đi khi khiến cho đồ thị không còn đẹp là người thua cuộc. Bạn hãy giúp Kiên và Thế xác định người chiến thắng nếu cả hai người đều chơi tối ưu.

Input

Dòng đầu tiên gồm một số nguyên dương ~T (1 \leq T \leq 10^{5})~ là số bộ dữ liệu trong input.

Trong mỗi bộ dữ liệu có:

  • Dòng đầu tiên gồm hai số nguyên ~N (1 \leq N \leq 10^{5})~ và ~M (1 \leq M \leq min(N \cdot (N-1) / 2, 10^{5}))~
  • Trong ~M~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~a_i~ và ~b_i (1 \leq a_i, b_i \leq N)~ biểu diễn một cạnh có sẵn trong đồ thị của Kiên

Tổng của ~N~ và ~M~ trong tất cả các test không vượt quá ~2 \cdot 10^{5}~.

Output

In ra ~T~ dòng tương ứng với ~T~ bộ dữ liệu. Nếu Kiên thắng trò chơi in ra "Kien", ngược lại Thế thắng thì in ra "The".

Sample Input

4
3 0
6 2
1 2
2 3
2 0
15 10
12 14
8 3
10 1
14 6
12 6
1 9
13 1
2 5
3 9
7 2

Sample Output

Kien
The
The
Kien

Comments

Please read the guidelines before commenting.


There are no comments at the moment.