K에 의해 나눠진 두 matrix 를 따로 생각해보자

일단 오른쪽 matrix 를 본다고 했을 때 각 열마다 min , max 값들을 pair 로 저장함

그리고 정렬을 하면 SCC 처럼 각 component 마다 묶이게 되고 일렬로 component 가 가르키게 됨.

예를 들면 (1,4) , (2,3) , ( 3,5) 는 다 같은 component 임 왜냐하면 이 중 어떤게 선택되도 나머지가 다 선택되야 하니깐

즉 (1,4 ) (5,6) (7,9) 이런 예시에선 component 가 3개이고 (1,4) -> (5,6) -> (7,9) 이렇게 연결되게 됨

그런 다음 왼쪽 matrix 에서 정당성 판별해주면 끗

시간복잡도는 n*m log ( n)