Organizing Party

시간 제한2초메모리 제한1024 MB

요약
양쪽 크기가 다른 이분 acquaintance 그래프에서 최대 7번의 이웃 집합 질의만으로 차수가 1이 아닌 손님 한 명을 찾는다.
난이도

어려움10점 중 8점

유형
그래프, 이분 탐색, 분할 정복, 구간
정답자
아직 제출이 없습니다

문제

Pak Dengklek is organizing a party at his place. This party is attended by N+MN + M guests, numbered 11 to N+MN + M. The guests numbered 11 to NN are male guests, while the guests numbered N+1N + 1 to N+MN + M are female guests.

Each guest gets acquainted with zero or more other guests that have the opposite gender. If the guest xx gets acquainted with guest yy, then guest yy also gets acquainted with guest xx. Since the duration of the party is quite short, usually each guest gets acquainted by exactly one other guest. A guest is said to be unusual if the guest does not get acquainted with other guests or gets acquainted with more than one other guests.

After checking the guest list, Pak Dengklek notices that the number of male guests is not the same as the number of female guests. Therefore, there must be at least one unusual guest. You want to help Pak Dengklek to identify any unusual guest.

You can ask at most 77 questions to Pak Dengklek. For each question, you can ask a set of guests. Pak Dengklek will answer the set of guests that get acquainted with at least one guest in the set. In other words, if you ask a set of guests AA, then a guest yy will be in the set answered by Pak Dengklek if and only if there is a guest xx in the set AA and guest xx gets acquainted with guest yy.

예제1

  1. 예제 1

    입력
    3 5
    
    7 1 2 3 4 5 6 8
    
    4 4 5 6 8
    
    3 1 2 3
    
    2 1 4
    
    
    예상 출력
    
    ? 8 1 2 3 4 5 6 7 8
    
    ? 3 1 2 3
    
    ? 5 4 5 6 7 8
    
    ? 2 1 4
    
    ! 7