ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1487. Китайский футбол

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В свободное время от контестов, игры в настольный футбол и просмотра кинофильмов Серёга с Денисом решили посещать один из многочисленных спортбаров Петрозаводска. Дело в том, что как раз в то время, когда проходят сборы, в китайском чемпионате по футболу состоится очередной тур. Серёга и Денис решили посмотреть наиболее интересные его матчи. В китайском чемпионате по футболу участвует N команд. Каждая команда должна сыграть с каждой ровно один раз. Хотя страсти на трибунах кипят нешуточные, чемпионат довольно скучен: если команда A победила команду B, а B победила C, то A либо уже победила C, либо точно победит C. В этом случае будем говорить, что A сильнее B и C (более формально, A сильнее B, если A обыграла B либо A обыграла некоторую команду C, а C сильнее B). При этом ничьих в матчах не бывает.
Денис и Серёга поспорили, какая китайская команда лучше других играет в футбол. Денис утверждает, что команда «Katraps» играет лучше команды «Kolomotiv». В качестве доказательства он привёл тот факт, что «Katraps» не слабее любой команды, которая сильнее команды «Kolomotiv». Разрешите их спор. Ваша задача - для каждой заданной пары команд достаточно быстро определять, играет ли первая лучше второй. Здесь термин «лучше» понимается так же, как понимает его Денис. Считается, что команда A не слабее команды B, если на данный момент нельзя сказать, что B сильнее A.

Исходные данные

В первой строке дано целое число N — количество команд, участвующих в чемпионате (2 ≤ N ≤ 1000). Все команды пронумерованы целыми числами от 1 до N. В следующих N строках записана турнирная таблица. Каждая строка таблицы состоит ровно из N символов. Если i-я и j-я команды уже сыграли друг с другом и i-я победила, то в i-й строке таблицы на j-й позиции стоит единица. Во всех остальных случаях в таблице стоят нули. Каждая пара команд сыграла не более одного матча. В следующей строке дано количество запросов Q ≤ 50000. Ввод завершается Q строками с запросами вида A B (1 ≤ AB ≤ N; A ≠ B).

Результат

Для каждого запроса нужно вывести «YES», если команда A играет лучше, чем команда B, и «No» иначе.

Пример

исходные данныерезультат
3
011
000
000
2
2 3
1 3
No
YES
Автор задачи: Сергей Пупырев
Источник задачи: XI Чемпионат УрГУ по программированию, 7 октября, 2006