Блэкджон
면접 대비시간 제한3초메모리 제한256 MB
n개의 분수 pi/qi가 주어질 때 값의 합이 정확히 1이 되는 카드 부분집합을 찾아 그 번호를 출력하고, 불가능하면 NO를 출력한다.
문제
С недавних пор блэкджек не приносит Джону былого удовольствия. Все вероятности давно просчитаны, оптимальная стратегия игры выработана. Поэтому Джон решил создать свою собственную модификацию этой игры — блэкджон.
Джон взял колоду карт и на каждой написал дробь pi⁄qi, по модулю не превосходящую единицу. Эта дробь называется значением карты. Правила таковы: игрок по очереди открывает карты из колоды и каждую либо берет в руку, либо сбрасывает. Для выигрыша необходимо добиться того, чтобы сумма значений карт в руке стала равной единице.
Джон хочет продемонстрировать новую игру друзьям, но у него есть серьезная проблема. Игра получилась настолько сложная, что даже зная заранее колоду карт, он не может определить, какие карты надо брать.
Джон попросил вас написать программу, которая по заданной колоде карт определит, какие карты надо брать в руку для того, чтобы выиграть.
입력
Первая строка содержит целое число n (1 ≤ n ≤ 100) — количество карт в колоде. Каждая из следующих n строк описывает одну из карт и содержит два разделенных пробелом целых числа pi и qi (1 ≤ qi ≤ 21, |pi| ≤ qi).
출력
В случае, если выиграть невозможно, выведите единственную строку NO.
В противном случае в первой строке выведите YES. Во второй строке выведите целое число m — количество карт в руке к концу игры. В третье строке выведите m чисел k1, k2, …, km — номера карт, сумма значений которых равна единице.
Карты нумеруются с единицы в порядке их перечисления во входном файле.