시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 131 25 16 27.119%

문제

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

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

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

입력

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

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

출력

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

예제 입력 1

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

예제 출력 1

1
IMPOSSIBLE
W3sicHJvYmxlbV9pZCI6IjUzNzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWMwNWMgXHVhY2ZjXHVkNTU5XHVjNzkwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMmU0XHVkNWQ4IFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWM4NzBcdWM3OTFcdWQ1NThcdWIyOTQgXHVhY2ZjXHVkNTU5XHVjNzkwXHVjNzc0XHViMmU0LiBcdWM4NzBcdWM3OTFcdWM3NDAgXHViOWU0XHVjNmIwIFx1YzJlMFx1YzkxMVx1ZDU1OFx1YWM4YyBcdWM5YzRcdWQ1ODlcdWQ1ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM5YzBcdWIwOWMgXHViYTg3IFx1YjE0NFx1YWMwNCBcdWFkZjggXHViMjA0XHVhZDZjXHVjNWQwXHVhYzhjXHViM2M0IFx1YWM3OFx1YjlhY1x1YzljMCBcdWM1NGFcdWM1NThcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjNzc0XHViODA3XHVhYzhjIFx1YzYyNFx1Yjc5YyBcdWFlMzBcdWFjMDQgXHVjNzU4XHVjMmVjXHVjNzQ0IFx1YmMxYlx1YzljMCBcdWM1NGFcdWIyZTRcdWJjZjRcdWIyYzggXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzgxMFx1YzgxMCBcdWM4NzBcdWM3OTFcdWM3NDQgXHViMzAwXHVjZGE5IFx1ZDU1OFx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWNkNWNcdWMyZTAgXHViMTdjXHViYjM4XHVjNWQwXHViMjk0IFx1YzExY1x1Yjg1YyBcdWJhYThcdWMyMWNcdWI0MThcdWIyOTQgXHVjNzc0XHViODYwXHVjNzc0IFx1YzIxOFx1Yjg1ZFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWJhYThcdWMyMWNcdWM3NDQgXHVjNWM2XHVjNTYwXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViMTdjXHViYjM4XHVjNWQwXHVjMTFjIFx1Yzc3Y1x1YmQ4MCBcdWM3NzRcdWI4NjBcdWM3NDQgXHVjODFjXHVhYzcwXHVkNTU4XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YjNkOVx1YjhjYyBcdWMxMjBcdWM5YzRcdWM3NzRcdWIyOTQgXHVhZGY4XHViM2Q5XHVjNTQ4IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWI5Y2VcdWM3NDAgXHVjMmU0XHVkNWQ4XHVjNzQ0IFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDQgXHViYWE4XHViNDUwIFx1YmNmNFx1YzU1OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWMxMjBcdWM5YzRcdWM3NzRcdWFjMDAgXHVjNzU4XHVjMmVjXHVkNTU4XHVhZTMwIFx1YzgwNFx1YzVkMCBcdWM4MWNcdWFjNzBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM3NzRcdWI4NjBcdWM3NTggXHVjMjE4XHViMjk0IFx1YzgxY1x1ZDU1Y1x1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKFx1Y2Q1Y1x1YjMwMCAxMDBcdWFjMWMpIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjE3Y1x1YmIzOFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjNzc0XHViODYwXHVjNzU4IFx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgNTApPFwvbGk+XHJcblx0PGxpPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzU4XHVjMmVjXHVjNzQ0IFx1YmMxYlx1YzljMCBcdWM1NGFcdWFjZTAgXHVjODFjXHVhYzcwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNzc0XHViODYwXHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMTgga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgayAmbGU7IDE2KTxcL2xpPlxyXG5cdDxsaT5cdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzExY1x1Yjg1YyBcdWJhYThcdWMyMWNcdWM3NzggXHVjNzc0XHViODYwXHVjNzU4IFx1YzMwZFx1Yzc1OCBcdWFjMWNcdWMyMTggbVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgbSAmbGU7IG4mdGltZXM7KG4tMSlcLzIpPFwvbGk+XHJcblx0PGxpPlx1YjJlNFx1Yzc0YyBtXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViYWE4XHVjMjFjXHVjNzc4IFx1Yzc3NFx1Yjg2MCB4PHN1Yj5pPFwvc3ViPlx1YzY0MCB5PHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgeDxzdWI+aTxcL3N1Yj4gJmx0OyB5PHN1Yj5pPFwvc3ViPiAmbGU7IG4pPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YmFhOFx1YzIxY1x1YjQxOFx1YjI5NCBcdWM3NzRcdWI4NjBcdWM3NzQgXHVjNWM2XHViMjk0IFx1YjE3Y1x1YmIzOFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzgxY1x1YWM3MFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjNzc0XHViODYwXHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1Yzc1OFx1YzJlY1x1Yzc0NCBcdWJjMWJcdWM3NDQgXHVjMjE4IFx1YmMxNlx1YzVkMCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHViNzdjXHViYTc0ICZxdW90O0lNUE9TU0lCTEUmcXVvdDtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjUzNzIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCYWQgU2NpZW50aXN0IiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIGEgcmF0aGVyIGZyYXVkdWxlbnQgc2NpZW50aXN0IHdobyBtYWtlcyB1cCBhbGwgaGlzIHJlc2VhcmNoIGRhdGEuIER1ZSB0byBjYXJlZnVsIHBsYW5uaW5nIHlvdSBnb3QgYXdheSB3aXRoIHRoaXMgZm9yIG1hbnkgeWVhcnMsIGJ1dCByZWNlbnRseSB5b3UgYmVjYW1lIHNsb3BweS4gSW4geW91ciBtb3N0IHJlY2VudCBwYXBlciB5b3UgY2FtZSB1cCB3aXRoIHNvIG1hbnkgdGhlb3JpZXMgdGhhdCBzb21lIGV2ZW4gY29udHJhZGljdCBlYWNoIG90aGVyLiBZb3Ugd2FudCB0byB0aHJvdyBhd2F5IGFzIGZldyB0aGVvcmllcyBhcyBwb3NzaWJsZSBzdWNoIHRoYXQgbm8gY29udHJhZGljdGluZyBwYWlyIHJlbWFpbnMuPFwvcD5cclxuXHJcbjxwPlRoZXJlIGlzIGEgcHJvYmxlbSBob3dldmVyOiB5b3VyIGNvbGxlYWd1ZXMgaGF2ZSBzZWVuIHlvdSBkb2luZyBhIGxvdCBvZiByZXNlYXJjaC4gVGhlcmUgaXMgYSBsaW1pdCBvbiBob3cgbWFueSB0aGVvcmllcyB5b3UgY2FuIHRocm93IGF3YXkgYmVmb3JlIHRoZXkgZ2V0IHN1c3BpY2lvdXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgXHVmYjAxcnN0IGxpbmUgb25lIHBvc2l0aXZlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYW4gaW50ZWdlciBuICgxICZsZTsgbiAmbGU7IDUwKTogdGhlIG51bWJlciBvZiB0aGVvcmllcyBpbiB0aGUgcGFwZXIuPFwvbGk+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYW4gaW50ZWdlciBrICgxICZsZTsgbiAmbGU7IDUwKTogdGhlIG1heGltdW0gbnVtYmVyIG9mIHRoZW9yaWVzIHRoYXQgY2FuIGJlIGRpc2NhcmRlZCB3aXRob3V0IGFyb3VzaW5nIHN1c3BpY2lvbi48XC9saT5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIG0gKDAgJmxlOyBtICZsZTsgbiZ0aW1lczsobi0xKVwvMik6IHRoZSBudW1iZXIgb2YgdGhlb3J5IHBhaXJzIHRoYXQgY29udHJhZGljdCBlYWNoIG90aGVyLjxcL2xpPlxyXG5cdDxsaT5tIGRpc3RpbmN0IGxpbmVzIHdpdGggdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyB4PHN1Yj5pPFwvc3ViPiBhbmQgeTxzdWI+aTxcL3N1Yj4gKDEgJmxlOyB4PHN1Yj5pPFwvc3ViPiZuYnNwOyZsdDsgeTxzdWI+aTxcL3N1Yj4mbmJzcDsmbGU7IG4pLCBpbmRpY2F0aW5nIHRoZW9yeSB4PHN1Yj5pPFwvc3ViPiBhbmQgdGhlb3J5IHk8c3ViPmk8XC9zdWI+IGFyZSBjb250cmFkaWN0b3J5LjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIHRoZSBtaW5pbWFsIG51bWJlciBvZiB0aGVvcmllcyB0aGF0IGhhdmUgdG8gYmUgZGlzY2FyZGVkIHRvIG1ha2UgYSBjb25zaXN0ZW50IHBhcGVyIG9yIHRoZSB3b3JkICZsZHF1bztJTVBPU1NJQkxFJnJkcXVvOyBpZiB0aGlzIGlzIGltcG9zc2libGUgd2l0aG91dCBhcm91c2luZyBzdXNwaWNpb24uPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=