알고리즘 캠프에 N명의 학생들이 있다. 이 학생들 중에서는 친한 사이도 있고 어색한 사이도 있다.

선생님은 N명의 학생들끼리 어색한 정도 F(i, j)를 표로 만들었다. 이때 F(i, j)는 i번 학생과 j번 학생 간의 어색한 정도를 의미한다. 모든 학생들의 쌍 (i, j)에 대해서 F(i, j)는 F(j, i)이다.

선생님은 일부 학생들끼리 떠들면 학업 분위기를 해칠 염려가 있어서 친한 친구들의 모임을 찾아서 감시하려고 한다. 이때 친한 친구들의 모임은 아래 조건을 만족해야 한다.

1. 친한 친구들의 모임은 2명 이상 N-1명 이하의 학생들로 구성되어야 한다.

2. 친한 친구들의 모임에서 가장 어색한 두 학생이 어색한 정도가 친한 친구들의 모임에 소속된 학생과 그렇지 않은 학생 간의 어색한 정도보다 항상 낮아야 한다.

예를 들어, A와 B와 C가 있어서 F(A, B) = 8, F(B, C) = 3, F(C, A) = 5라고 하자. 이때 A와 C가 있는 모임은 C가 A보다 B에게 친함을 느끼므로 친한 친구들의 모임이 아니다. 한편 B와 C가 있는 모임은 B, C 간의 사이가 가장 친하므로 친한 친구들의 모임이다.

선생님은 가능한 친한 친구들의 모임을 전부 구하려고 한다. N명의 학생들 사이의 어색한 정도가 주어질 때 가능한 친한 친구들의 모임의 수를 구하는 프로그램을 작성하여라.

#2973 upload 22 done - how_to_reg -

친구들 timer 3s memory 64MB

#2973

친구들 3s 64MB