Махмуд хочет составить новый словарь, содержащий n слов и отношения между ними. Бывает два типа отношений: синонимичность (что значит, что два слова означают одно и тоже) и антонимичность (что значит, что два слова означают противоположные вещи). Время от времени он узнает новые отношения между некоторыми словами.

Махмуд знает, что если между двумя словами есть отношение, то каждое из этих слов имеет отношения со всеми словами, которые имеют отношения к другому слову из пары. Например, если like означает то же, что и love, и love — противоположность hate, то like — тоже противоположность hate. Еще один пример: если love — противоположность hate, и hate — противоположность like, то love — то же, что и like, и так далее.

Иногда Махмуд узнает неверное отношение. Неверное отношение это такое отношение, которое делает два слова одним и тем же и противоположностями одновременно. Например, если он знает, что love — то же, что и like, и like — противоположность hate, и затем узнает, что hate — то же, что и like, то последнее отношение, конечно, неверное, потому что оно делает hate и like антонимами и синонимами одновременно.

После того, как Махмуд узнал много отношений между словами, он обеспокоился тем, что некоторые отношения могут быть неверными. Он решил рассказать о каждом отношении знакомому программисту Ехабу. Махмуд хочет знать для каждого отношения, верное оно или неверное, основываясь на отношениях, которые он узнал раньше. Если отношение неверное, то Махмуд его игнорирует и не использует его для проверки последующих отношений.

После того, как Махмуд расскажет о всех отношениях, он спросит Ехаба об отношениях между некоторыми словами, основываясь на информации, которую дал. Ехаб занят подготовкой раунда Codeforces, поэтому вы должны ему помочь.