만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

두 번의 회의 일정 잡기

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

요약
시간 슬롯마다 m명 심사위원의 현장 참석 여부가 주어질 때, 모든 심사위원이 두 회의 중 하나에 현장으로 참석하고 두 회의에 모두 참석하는 인원이 가장 많은 슬롯 쌍을 고릅니다.
난이도

보통10점 중 6점

유형
비트 연산, 동적 계획법
정답자
아직 제출이 없습니다

문제

당신은 올해 국제 대학생 퀴즈 대회(ICQC)의 수석 심사위원장이다. 대회 문제 세트를 준비하기 위해 심사위원 회의를 두 번 열려고 한다. 후보 일정을 여러 개 제시했고, 심사위원 전원이 시간대마다 현장에 참석할지, 화상 회의 도구로 원격 참석할지 답했다.

서로 다른 두 시간대를 골라, 모든 심사위원이 두 회의 중 적어도 하나에는 현장에서 참석하도록 해야 한다. 조건을 만족하는 쌍이 여러 개면 두 회의에 모두 현장 참석하는 심사위원 수가 가장 많은 쌍을 고른다. 그래도 같으면 첫 번째 회의가 더 이른 쌍을 고른다. 첫 번째 회의도 같으면 두 번째 회의가 더 이른 쌍을 고른다.

입력

첫 줄에 정수 nn과 mm이 주어진다. nn(2≤n≤2×1052 \le n \le 2 \times 10^5)은 후보 시간대의 수이며, 1번부터 nn번까지 번호가 붙는다. 번호가 작을수록 이른 시간대다. mm(2≤m≤202 \le m \le 20)은 심사위원의 수다.

이어지는 nn개의 줄에는 각각 mm개의 문자가 주어진다. ai,ja_{i,j}가 Y이면 ii번 시간대에 jj번 심사위원이 현장에 참석한다는 뜻이고, N이면 원격으로 참석한다는 뜻이다.

출력

최적의 쌍에 속한 두 시간대 번호를 공백으로 구분해 한 줄에 출력한다. 이른 시간대를 먼저 쓴다. 조건을 만족하는 쌍이 없으면 No를 출력한다.

예제5

  1. 예제 1

    입력
    4 3
    NNY
    YYN
    YNY
    NYY
    
    예상 출력
    2 3
    
  2. 예제 2

    입력
    3 6
    NNNYYY
    YYNYYN
    YYYNNN
    
    예상 출력
    1 3
    
  3. 예제 3

    입력
    6 5
    NNNNN
    YNNNY
    YYNNN
    YYNNN
    NYYNY
    NNYYY
    
    예상 출력
    3 6
    
  4. 예제 4

    입력
    3 3
    YNN
    NYN
    NNY
    
    예상 출력
    No
    
  5. 예제 5

    입력
    4 4
    NYNN
    YNYY
    YNYN
    NNYY
    
    예상 출력
    1 2