아이싱

수많은 중고등학생들에게 아이싱이라는 온라인 일대일 대전 게임이 유행하고 있다. 게임회사에서는 이 게임을 확장하여 팀 I와 팀 Sing 사이에 대전을 할 수 있는 팀플레이 전용 아이싱II를 개발하였다. 아이싱II는 게이머들의 기존 아이싱에서의 대전 이력을 활용하여 독특한 방식으로 팀을 구성하도록 설계되었다. 즉, 아이싱에서 일대일 대전을 한 두 게이머는 서로 다른 팀에 속해야 한다. 각 팀의 인원수는 1명 이상이며 두 팀의 인원수는 서로 달라도 된다.

예를 들어, 아래 표는 네 명의 게이머 A, B, C, D가 아이싱에서 일대일 대전을 한 기록을 이용하여 아이싱II의 팀을 구성한 예이다.

<예시 1>

그런데, 이제 3분 후면 아이싱II 서버 오픈인데 치명적인 문제가 발견되었다. 예를 들어, 게이머 A, B, C가 모두 서로 대전한 적이 있다면 각각 다른 팀에 들어가야 하므로 팀 I와 팀 Sing 구성이 불가능한 것이다.

이 문제를 해결하기 위해 다음과 같은 해법을 적용하려 한다. 바로 아이싱 대전 기록 중 최소 개수의 대전 기록을 지우는 것이다. 예를 들어, 아래 그림과 같이 네 명의 게이머 A, B, C, D의 아이싱에서 일대일 대전 기록이 주어질 때(왼쪽)를 생각해 보자. 이 경우 최소 하나의 기록을 지워야 하며, 대전 기록 중 A – B를 지운다면(가운데) 두 팀 구성이 가능하다(오른쪽).

<예시 2>

다른 예로, 다음과 같은 아이싱 대전 기록을 생각해 보자. 이 경우 최소 두 개의 대전 기록을 지워야 하며, A – B와 C – D를 지운다면 아래와 같이 두 팀을 구성할 수 있다.

<예시 3>

하지만, 게임의 런칭이 3분 밖에 남지 않았기 때문에 지울 수 있는 기록의 개수는 최대 두 개로 한정된다. 만약에 3개 이상의 기록을 지워야 한다면 런칭을 지연하는 것이 더 좋을 수도 있다.

이 와중에 게임회사 대표는 두 팀을 구성하기 위해 지울 수 있는 최소 크기의 대전 기록 집합이 얼마나 다양하게 존재하는지 궁금해졌다. 즉, 최소로 지워야 하는 대전 기록의 개수가 $K$ 일 때, 크기 $K$ 인 지울 수 있는 대전 기록의 부분집합의 경우의 수를 세어야 한다.

<예시 2>에서는 {A – B}, {A - C}, 또는 {B – C}를 지우면 최소 개수의 대전 기록을 지우면서 두 팀을 구성할 수 있다. 이 경우의 답은 3이다. <예시 3>에서는 {A – B, C – D}, {A – C, B – D}, 또는 {A – D, B – C}를 지우면 최소 개수의 대전 기록을 지우면서 두 팀을 구성할 수 있다. 이 경우의 답은 3이다.

여러분은 주어진 아이싱 대전 기록을 이용하여 두 팀을 구성할 수 있도록 지울 수 있는 최소 개수의 대전 기록을 선택하는 서로 다른 방법의 개수를 구하기 위해서 다음 함수를 구현해야만 한다. 이때 지울 대전 기록의 선택 순서는 중요하지 않다. 또한, 2개 이하의 대전 기록을 지워서 게임을 진행할 수 없다면, 0을 반환한다. 만약, 아무 기록도 지워야 할 필요가 없다면, 아무 것도 안 지우는 것이 가장 빠른 유일한 방법이니 방법의 개수는 1이다.

long long count_ways( int N, vector<int> U, vector<int> V ) ; N은 게이머 수, U와 V는 크기 M인 vector로 U[i]와 V[i] 사이에 아이싱 대전 기록이 존재한다. 이를 이용하여 지울 최소 크기의 대전 기록을 선택하는 서로 다른 방법의 개수를 구하여 return한다. 단, 3개 이상의 기록을 지워야만 한다면 0을 return한다.

문제

제한