시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 118 20 12 24.000%

문제

상근이는 실험 결과를 조작하는 과학자이다. 조작은 매우 신중하게 진행했기 때문에, 지난 몇 년간 그 누구에게도 걸리지 않았다. 하지만, 이렇게 오랜 기간 의심을 받지 않다보니 상근이는 점점 조작을 대충 하게 되었다.

상근이의 최신 논문에는 서로 모순되는 이론이 수록되어 있다. 이러한 모순을 없애기 위해서 상근이는 논문에서 일부 이론을 제거하기로 했다.

상근이의 동료 선진이는 그동안 상근이가 많은 실험을 하는 것을 모두 보았다. 따라서, 선진이가 의심하기 전에 제거할 수 있는 이론의 수는 제한되어 있다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. (최대 100개) 각 테스트 케이스는 다음과 같이 구성되어 있다.

  • 첫째 줄에 논문에 있는 이론의 수 n이 주어진다. (1 ≤ n ≤ 50)
  • 둘째 줄에는 의심을 받지 않고 제거할 수 있는 이론의 최대 개수 k가 주어진다. (0 ≤ k ≤ 16)
  • 셋째 줄에는 서로 모순인 이론의 쌍의 개수 m이 주어진다. (0 ≤ m ≤ n×(n-1)/2)
  • 다음 m개 줄에는 서로 모순인 이론 xi와 yi가 주어진다. (1 ≤ xi < yi ≤ n)

출력

각 테스트 케이스에 대해서, 모순되는 이론이 없는 논문을 만들기 위해서 제거해야 하는 이론의 최소 개수를 출력한다. 만약, 의심을 받을 수 밖에 없는 경우라면 "IMPOSSIBLE"을 출력한다.

예제 입력

2
5
5
2
1 3
2 3
3
1
3
1 2
2 3
1 3

예제 출력

1
IMPOSSIBLE

힌트