1429번 - 결혼

문제

항승이네 마을에서 결혼이란 일반적인 결혼과는 약간 다르다. 항승이네 마을에서 결혼이란 한 명의 남편과 여러 명의 부인, 또는 여러 명의 남편과 한 명의 부인을 의미한다.

항승이네 마을에 남자가 총 N명, 여자가 총 M명 있다. 어떤 남자와 어떤 여자가 결혼을 하려면, 서로가 서로에게 호감이 있어야 한다.

항승이가 마을의 촌장으로써 할 일은 남자와 여자를 결혼을 시키는 것인데, 가능한 결혼의 개수를 최소화시키는 것이다. 모든 사람은 반드시 하나의 결혼을 해야만 한다. 즉, 결혼을 하지 않는 경우는 없다. 그 때 가능한 결혼의 수의 최솟값을 구하는 프로그램을 작성하시오. 모든 사람이 결혼을 할 수 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 12보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에는 i번 남자와 1,2,3,...M번 여자가 호감이 있으면 1 없으면 0이 주어진다.

출력

첫째 줄에 결혼의 개수의 최솟값을 출력한다. 만약 모든 사람이 결혼을 할 수 없으면 -1을 출력한다.

제한

힌트