Задача G. Камень, ножницы, бумага и другие ≡

Условие

Глеб и Вася, студенты Института математики и компьютерных наук ДВФУ, часто играют в игру "камень, ножницы, бумага", чтобы определить, кто пойдёт мыть тряпку для стирания с доски.

Правила этой игры таковы: участники произносят фразу "камень, ножницы, бумага раз, два, три", после чего каждый участник показывает рукой один из трёх предметов: камень, ножницы или бумагу. В игре считается, что камень ломает ножницы, ножницы режут бумагу, бумага накрывает камень. Если, например, Глеб выбрал бумагу, а Вася выбрал ножницы, то Вася побеждает, а если оба игрока выбрали камень, то объявляется ничья.

Однажды Глеб и Вася захотели обобщить игру "камень, ножницы, бумага". Теперь в игре задействовано N предметов. Задаётся список пар предметов. Считается, что если один игрок выбрал первый предмет из некоторой пары, а другой игрок — второй предмет из этой пары, то тот, кто выбрал первый предмет из пары, побеждает. Если игроки выбрали пару предметов, которая не встречается в списке пар, то объявляется ничья.

Напишите программу, принимающую на вход список предметов, список пар предметов и список игр и выводящую результаты игр.

Рекомендуется рассмотреть частичные решения

1 ≤ M, K ≤ 200

Формат входного файла

Первая строка входного файла содержит целое число N — количество предметов. Далее следуют N строк — названия предметов. Длина названия составляет от 1 до 20 символов. Названия состоят из маленьких латинских букв. Все названия различны.

Следующая строка содержит целое число M — длину списка пар предметов. Далее следуют 2 × M строк — пары предметов. В каждой из этих строк может содержаться только название предмета из списка предметов. Никакие два предмета не могут содержаться одновременно в двух парах.

Следующая строка содержит целое число K — количество игр. Далее следуют 2 × K строк. В каждой из этих строк может содержаться только название предмета из списка предметов.

Формат выходного файла

Выходной файл должен содержать K чисел. Для каждой игры должно быть выведено число 1, если выиграл первый игрок, число 2, если выиграл второй игрок, и число 0, если игроки сыграли вничью.

Ограничения

2 ≤ N ≤ 1000

1 ≤ M, K ≤ 20000

Примеры тестов

3
kamen
nozhnitsy
bumaga
3
kamen
nozhnitsy
nozhnitsy
bumaga
bumaga
kamen
2
bumaga
nozhnitsy
kamen
kamen

2 0