Làng Ma Sói

Time limit: 1.0s Memory limit: 256M Read editorial

Problem

Tối nào dân làng Gió Hú cũng tụ tập chơi Ma Sói. Mỗi người chơi thuộc đúng một trong hai phe: Dân làng hoặc Ma sói. Không ai biết ai thuộc phe nào, chỉ biết chắc chắn là chỉ có hai phe.

Năm nay làng mời được thám tử Mèo Mun về làm người dẫn trò. Mèo Mun ngồi một góc, lắng nghe và ghi chép lại \(q\) dòng thông tin theo đúng thứ tự xuất hiện. Mỗi dòng có một trong ba dạng:

  • SAME A B: một lời khai nói rằng \(A\) và \(B\) cùng phe.
  • DIFF A B: một lời khai nói rằng \(A\) và \(B\) khác phe.
  • ASK A B: trưởng làng hỏi Mèo Mun: "\(A\) và \(B\) có cùng phe không?".

Mèo Mun luôn giữ một danh sách các lời khai mà mình tin. Ban đầu danh sách này rỗng. Ta gọi một cách chia phe là một cách xếp mỗi người vào một trong hai phe, và nói cách chia đó hợp lệ nếu nó thỏa mãn mọi lời khai Mèo Mun đang tin.

Khi gặp một lời khai về \(A\) và \(B\), Mèo Mun trả lời:

  • LIE nếu không có cách chia phe hợp lệ nào thỏa mãn lời khai mới. Lời khai này bị coi là nói dối và bị bỏ qua.
  • KNOWN nếu mọi cách chia phe hợp lệ đều đã thỏa mãn lời khai mới, tức là Mèo Mun đã tự suy ra được điều này từ trước.
  • NEW trong các trường hợp còn lại. Mèo Mun tin lời khai này và thêm nó vào danh sách.

Khi gặp một câu hỏi về \(A\) và \(B\), Mèo Mun trả lời:

  • SAME nếu trong mọi cách chia phe hợp lệ, \(A\) và \(B\) đều cùng phe;
  • DIFF nếu trong mọi cách chia phe hợp lệ, \(A\) và \(B\) đều khác phe;
  • UNKNOWN nếu chưa thể kết luận.

Một vài điều cần lưu ý:

  • Mỗi người luôn cùng phe với chính mình.
  • Người được hỏi có thể chưa từng xuất hiện trong lời khai nào.
  • Tên người chơi phân biệt chữ hoa và chữ thường: Lan, lan và LAN là ba người khác nhau (làng Gió Hú rất đông dân và trùng tên khá nhiều).

Hãy giúp Mèo Mun trả lời tất cả các dòng thông tin trước khi trời sáng nhé.

"Kẻ thù của kẻ thù là bạn. Kẻ thù của kẻ thù của kẻ thù... thì cứ đếm cho kỹ."

-- Thám tử Mèo Mun

Input

  • Dòng đầu tiên gồm một số nguyên \(q\) \((1 \leq q \leq 10^5)\) là số dòng thông tin.
  • \(q\) dòng tiếp theo, mỗi dòng có dạng SAME A B, DIFF A B hoặc ASK A B. Tên \(A\), \(B\) dài từ \(1\) đến \(10\) ký tự, chỉ gồm chữ cái tiếng Anh (hoa và thường) và chữ số. \(A\) và \(B\) có thể trùng nhau.

Output

  • Với mỗi dòng thông tin, in ra câu trả lời của Mèo Mun trên một dòng: NEW, KNOWN hoặc LIE cho lời khai; SAME, DIFF hoặc UNKNOWN cho câu hỏi.

Sample

#InputOutput
1
8
SAME An Binh
DIFF Binh Cuong
ASK An Cuong
SAME An Cuong
DIFF Cuong An
ASK Binh Dung
DIFF Dung Dung
ASK Dung Dung
NEW
NEW
DIFF
LIE
KNOWN
UNKNOWN
LIE
SAME
2
6
DIFF Soi1 Dan
DIFF Dan Soi2
ASK Soi1 Soi2
SAME Soi1 Soi2
DIFF lan Lan
ASK lan LAN
NEW
NEW
SAME
KNOWN
NEW
UNKNOWN

Note

Sample 1:

  1. SAME An Binh: chưa biết gì về hai người này, Mèo Mun tin lời khai → NEW.
  2. DIFF Binh Cuong: cũng là thông tin mới → NEW.
  3. ASK An Cuong: An cùng phe với Binh, Binh khác phe với Cuong, nên An chắc chắn khác phe với Cuong → DIFF.
  4. SAME An Cuong: trái với điều vừa suy ra → LIE, lời khai bị bỏ qua.
  5. DIFF Cuong An: điều này Mèo Mun đã biết → KNOWN.
  6. ASK Binh Dung: Dung chưa từng xuất hiện → UNKNOWN.
  7. DIFF Dung Dung: không ai khác phe với chính mình → LIE.
  8. ASK Dung Dung: ai cũng cùng phe với chính mình → SAME.

Sample 2: Soi1 khác phe với Dan, Dan khác phe với Soi2. Vì chỉ có hai phe nên Soi1 và Soi2 chắc chắn cùng phe. Ở hai dòng cuối, lan, Lan và LAN là ba người khác nhau, và chưa có lời khai nào nhắc tới LAN.


Comments

There are no comments at the moment.

Code editor