Jigsaw Present

시간 제한5초메모리 제한2048 MB

요약
조각 수와 난이도가 주어진 n개의 퍼즐에서 총 조각 수와 총 난이도가 모두 같은 서로 다른 두 부분집합을 찾거나, 선물이 유일하다고 판정한다.
난이도

어려움10점 중 8점

유형
해시맵, 동적 계획법, 완전 탐색
정답자
아직 제출이 없습니다

문제

Julia is preparing a present for James. She will give him some of her nn jigsaw puzzles, where puzzle ii (1≤i≤n1 \leq i \leq n) consists of x_ix\_i pieces and has a difficulty y_iy\_i (can be negative if the puzzle is very easy).

James is already very excited and would like to know in advance what he will get. Therefore, he used some of his criminal energy to gather information about the gift. In particular, he has managed to obtain an encrypted message containing the total difficulty and total number of pieces of all the puzzles that he will receive.

Now he wonders whether it is worth spending some more time to decrypt the message. After all, it might be that this information is not enough to uniquely determine his gift. Since he was never good at these computer thingies, James asked for your assistance. Help him find out whether it is worth decrypting the message or not. If the answer is negative, you have to find two distinct gifts that result in the same encrypted message.

입력

The input consists of

  • One line with an integer nn (2≤n≤4,0962 \leq n \leq 4\\,096), the number of puzzles that Julia owns.
  • nn lines, the iith of which contains two integers x_ix\_i and y_iy\_i (1≤x_i≤4,0961 \leq x\_i \leq 4\\,096, ∣y_i∣≤4,096\left|y\_i\right| \leq 4\\,096), the number of pieces of puzzle ii and the difficulty of puzzle ii.

출력

If James can uniquely determine his gift, then print "yes". Otherwise, you should print "no" followed by two lines, where each line contains the description of a present. The description of a present should start with an integer kk, the number of puzzles, followed by kk distinct integers, the indices of the puzzles.

Note that the two presents have to be distinct, meaning that there should be at least one puzzle that is contained in one present but not the other.

If there are multiple presents that result in the same encrypted message, you can print any of them.

예제2

  1. 예제 1

    입력
    5
    2 -1
    3 2
    3 1
    1 -3
    1 1
    
    예상 출력
    no
    3 2 4 5
    2 1 3
    
  2. 예제 2

    입력
    4
    2 -1
    3 2
    3 1
    1 -3
    
    예상 출력
    yes