아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Boxers

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

요약
토너먼트 경기 결과 행렬이 주어질 때, 두 선수를 제거한 뒤 남은 결과가 강한 선수가 항상 이긴다는 규칙과 일치하도록 하는 두 선수를 찾는다.
난이도

보통10점 중 5점

유형
그래프, 정렬, 그리디
정답자
아직 제출이 없습니다

문제

A boxing club has NN members, numbered 1,…,N1, \ldots, N. Each member has a fixed strength. The strengths are unique integers with unknown values.

In a boxing match, a stronger boxer always beats a weaker one... or rather, would beat in an honest match. The thing is, there are two cheaters in the club. They use illegal tricks and could beat any honest boxer. To avoid suspicion, each of them picks (independently from the other) a number of honest boxers; in subsequent matches, they will always win against the chosen boxers and deliberately lose against all others. The cheaters also agree on who will win when they meet each other in a match.

Now the coach has caught wind of the scheme and wants to expel the cheaters. For that, he arranged a tournament where each member met each other in a match. However, the club has many members, and the coach can't program, so he has asked you to help.

You are given the results of the tournament and need to find two members such that when these two are removed, the results of the remaining boxers are consistent with the "a stronger boxer always beats a weaker one" rule. If there are several possible solutions, output any one of them. The coach is not much of a justice warrior, he mainly just wants to blame someone...

입력

The first line contains NN (3≤N≤3⋅1033 \le N \le 3 \cdot 10^3), the number of boxers. The following NN lines present a table consisting of 0, 1, and x. If the ii-th boxer won against the jj-th, then the table has 1 in the ii-th row of the jj-th column and 0 in the jj-th row of the ii-th column.

출력

Output two space-separated integers, the numbers of the cheaters, in any order. All the inputs are such that a solution exists.

예제2

  1. 예제 1

    입력
    6
    x00011
    1x1011
    10x111
    110x10
    0000x1
    00010x
    
    예상 출력
    1 4
    
  2. 예제 2

    입력
    11
    x1111010010
    0x000001001
    01x11011011
    010x0001001
    0101x010011
    11111x10111
    010100x0001
    1000111x011
    11111011x11
    010100100x0
    1000000001x
    
    예상 출력
    8 11