Жила-была девочка катя, и было у неё много-много денег. и подруг. ну как
и собрались они как-то раз все вместе у кати дома и обсуждали фильмы. многие хвалили вкус кати. редко кто не соглашался с её мнением. о вкусах, конечно, не спорят, но кате показалось это странным и она решила устроить проверку.
катя записала m пар фильмов, которые девочки сравнивали, и для каждой такой пары пометила, какой из фильмов девочки посчитали однозначно лучше другого. а потом воспользовалась своим обаянием влиянием и убедила школьного психолога провести тестирование, в котором есть вопрос о трёх любимых фильмах. вот так вот всё просто, когда ты – катя.
среди неиспорченных бланков тестирования (не спрашивайте, как она их достала) катя нашла заполненные бланки n своих подруг. скажите, согласовываются ли записи кати с каждым из ответов на вопрос о трёх любимых фильмах в отдельности.
формат входных данных
в первой строке заданы числа n и m (1≤n,m≤1000).
в следующих m строках – пары фильмов, записанные у кати. первый фильм в паре считается лучше второго.
в следующих n строках – списки любимых фильмов девочек. первый фильм в тройке считается лучше второго, а второй – лучше третьего.
записи кати непротиворечивы. каждая пара фильмов в записях кати встречается не более одного раза.
так сложилось, что все фильмы, что встречаются в списках любимых фильмов девочек, встречаются и в записях кати, а в каждом отдельно взятом списке все три фильма различны.
для вашего же удобства названия фильмов во входных данных заменены на положительные натуральные числа, не превышающие 106.
формат выходных данных
выведите n строк, в i-ой из которых должно быть написано honest, если список любимых фильмов из i-го бланка не противоречит записям кати, или liar, если противоречит.
не выводите лишние пробелы в конце или начале строк - это будет считаться за ошибку.
пояснение к примеру
тройка фильмов 1 2 4 противоречит записям кати, так как по записям кати фильм 5 лучше фильма 4, но его нет в тройке.
тройка фильмов 1 3 2 противоречит, так как по записям кати фильм 2 лучше фильма 3, а в тройке фильм 3 стоит до фильма 2.
тройка фильмов 5 4 8 противоречит, так как по записям кати фильм 2 лучше фильма 4, но его нет в тройке.
sample input:
5 8
1 3
1 2
2 3
2 4
4 8
5 4
5 6
7 6
1 2 3
1 2 4
1 3 2
5 4 8
5 7 6
sample output:
honest
liar
liar
liar
honest
напишите программу. тестируется через stdin → stdout
time limit: 1 секунда
memory limit: 256 mb
