시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB153746929825.297%

문제

위대한 수학자 김선영은 선형대수학 교과서를 집필하는 과정에서 다음과 같은 문제를 만들었다.

\(N\times N\)행렬 \(A\)에 대해 다음 명제들이 동치임을 증명하라:

  1. \(A\)의 역행렬이 존재한다.
  2. 임의의 \(N\times 1\)행렬 \(b\)에 대해 \(Ax=b\)는 단 하나의 해만을 갖는다.
  3. 임의의 \(N\times 1\)행렬 \(b\)에 대해 \(Ax=b\)는 해를 갖는다.
  4. \(Ax=0\)의 해는 오직 \(x=0\)하나밖에 존재하지 않는다.

이런 문제를 해결하는 일반적인 방법은 일련의 함축(implication)을 이용하는 것이다.

예를 들어, 선영이의 예시 답안은

(a)이면 (b)이고, (b)이면 (c)이며 (c)이면 (d)이고, 마지막으로 (d)이면 (a)이다. 이 네 함축은 네 가지 명제가 동치임을 보여준다.

라고 되어있다.

다른 방법으로는 (a)이면 (b)이고, (b)이면 (a)이므로 (a)와 (b)가 동치라고 증명한 다음,

같은 방식으로 (b)와 (c)가 동치임을 증명하고, 마지막으로 (c)와 (d)가 동치임을 증명하는 방법이 있다.

하지만 이건 무려 여섯 번의 함축을 필요로 한다.

선영이는 선형대수학 책을 집필하는 과정에서 수없이 많은 명제가 동치임을 증명해야 하기 때문에 이러한 비효율성은 치명적이다.

선영이가 다음 학기 시작 전에 교재를 모두 집필할 수 있도록 되도록이면 적은 수의 함축을 이용해서 명제가 동치임을 증명할 수 있도록 도와주자.

입력

첫 번째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 100)가 주어지고,

각 테스트 케이스에 대해서는 다음과 같은 입력이 주어진다:

  • 명제의 수 n(1 ≤ n ≤ 20,000)와 이미 증명된 함축의 수 m(0 ≤ m ≤ 50,000)이 첫 번째 줄에 주어진다.
  • m개의 줄에 "s1이면 s2이다." 를 나타내는 s1과 s2(1 ≤ s1,s2 ≤ n이고 s≠ s2)가 주어진다.

출력

각 테스트 케이스마다 한 줄을 출력한다:

  • 위대한 수학자 김선영이 주어진 명제들이 동치임을 증명하기 위해 사용해야 하는 함축의 수의 최솟값.

예제 입력 1

2
4 0
3 2
1 2
1 3

예제 출력 1

4
2
W3sicHJvYmxlbV9pZCI6IjM2ODIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzZDlcdWNlNTggXHVjOTlkXHViYTg1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3MDRcdWIzMDBcdWQ1NWMgXHVjMjE4XHVkNTU5XHVjNzkwIFx1YWU0MFx1YzEyMFx1YzYwMVx1Yzc0MCBcdWMxMjBcdWQ2MTVcdWIzMDBcdWMyMThcdWQ1NTkgXHVhZDUwXHVhY2ZjXHVjMTFjXHViOTdjIFx1YzlkMVx1ZDU0NFx1ZDU1OFx1YjI5NCBcdWFjZmNcdWM4MTVcdWM1ZDBcdWMxMWMgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWJiMzhcdWM4MWNcdWI5N2MgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cXChOXFx0aW1lcyBOXFwpXHVkNTg5XHViODJjIFxcKEFcXClcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YjJlNFx1Yzc0YyBcdWJhODVcdWM4MWNcdWI0ZTRcdWM3NzQgXHViM2Q5XHVjZTU4XHVjNzg0XHVjNzQ0IFx1Yzk5ZFx1YmE4NVx1ZDU1OFx1Yjc3Yzo8XC9wPlxyXG5cclxuPG9sIHN0eWxlPVwibGlzdC1zdHlsZS10eXBlOmxvd2VyLWFscGhhXCI+XHJcblx0PGxpPlxcKEFcXClcdWM3NTggXHVjNWVkXHVkNTg5XHViODJjXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzg0XHVjNzU4XHVjNzU4IFxcKE5cXHRpbWVzIDFcXClcdWQ1ODlcdWI4MmMgXFwoYlxcKVx1YzVkMCBcdWIzMDBcdWQ1NzQgXFwoQXg9YlxcKVx1YjI5NCBcdWIyZTggXHVkNTU4XHViMDk4XHVjNzU4IFx1ZDU3NFx1YjljY1x1Yzc0NCBcdWFjMTZcdWIyOTRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1Yzc4NFx1Yzc1OFx1Yzc1OCBcXChOXFx0aW1lcyAxXFwpXHVkNTg5XHViODJjIFxcKGJcXClcdWM1ZDAgXHViMzAwXHVkNTc0IFxcKEF4PWJcXClcdWIyOTQgXHVkNTc0XHViOTdjIFx1YWMxNlx1YjI5NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XFwoQXg9MFxcKVx1Yzc1OCBcdWQ1NzRcdWIyOTQgXHVjNjI0XHVjOWMxIFxcKHg9MFxcKVx1ZDU1OFx1YjA5OFx1YmMxNlx1YzVkMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1Yzc3NFx1YjdmMCBcdWJiMzhcdWM4MWNcdWI5N2MgXHVkNTc0XHVhY2IwXHVkNTU4XHViMjk0IFx1Yzc3Y1x1YmMxOFx1YzgwMVx1Yzc3OCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjNzdjXHViODI4XHVjNzU4IFx1ZDU2OFx1Y2Q5NShpbXBsaWNhdGlvbilcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjMTIwXHVjNjAxXHVjNzc0XHVjNzU4IFx1YzYwOFx1YzJkYyBcdWIyZjVcdWM1NDhcdWM3NDA8XC9wPlxyXG5cclxuPGJsb2NrcXVvdGU+KGEpXHVjNzc0XHViYTc0IChiKVx1Yzc3NFx1YWNlMCwgKGIpXHVjNzc0XHViYTc0IChjKVx1Yzc3NFx1YmE3MCZuYnNwOyhjKVx1Yzc3NFx1YmE3NCAoZClcdWM3NzRcdWFjZTAsIFx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YyAoZClcdWM3NzRcdWJhNzQgKGEpXHVjNzc0XHViMmU0LiZuYnNwO1x1Yzc3NCBcdWIxMjQgXHVkNTY4XHVjZDk1XHVjNzQwIFx1YjEyNCBcdWFjMDBcdWM5YzAgXHViYTg1XHVjODFjXHVhYzAwIFx1YjNkOVx1Y2U1OFx1Yzc4NFx1Yzc0NCBcdWJjZjRcdWM1ZWNcdWM5MDBcdWIyZTQuPFwvYmxvY2txdW90ZT5cclxuXHJcbjxwPlx1Yjc3Y1x1YWNlMCBcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yjk3OCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWNcdWIyOTQgKGEpXHVjNzc0XHViYTc0IChiKVx1Yzc3NFx1YWNlMCwgKGIpXHVjNzc0XHViYTc0IChhKVx1Yzc3NFx1YmJjMFx1Yjg1YyAoYSlcdWM2NDAgKGIpXHVhYzAwIFx1YjNkOVx1Y2U1OFx1Yjc3Y1x1YWNlMCBcdWM5OWRcdWJhODVcdWQ1NWMgXHViMmU0XHVjNzRjLDxcL3A+XHJcblxyXG48cD5cdWFjMTlcdWM3NDAgXHViYzI5XHVjMmRkXHVjNzNjXHViODVjIChiKVx1YzY0MCAoYylcdWFjMDAgXHViM2Q5XHVjZTU4XHVjNzg0XHVjNzQ0IFx1Yzk5ZFx1YmE4NVx1ZDU1OFx1YWNlMCwmbmJzcDtcdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMgKGMpXHVjNjQwIChkKVx1YWMwMCBcdWIzZDlcdWNlNThcdWM3ODRcdWM3NDQgXHVjOTlkXHViYTg1XHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYyBcdWM3NzRcdWFjNzQgXHViYjM0XHViODI0IFx1YzVlY1x1YzEyZiBcdWJjODhcdWM3NTggXHVkNTY4XHVjZDk1XHVjNzQ0IFx1ZDU0NFx1YzY5NFx1Yjg1YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWMxMjBcdWQ2MTVcdWIzMDBcdWMyMThcdWQ1NTkgXHVjYzQ1XHVjNzQ0IFx1YzlkMVx1ZDU0NFx1ZDU1OFx1YjI5NCBcdWFjZmNcdWM4MTVcdWM1ZDBcdWMxMWMgXHVjMjE4XHVjNWM2XHVjNzc0IFx1YjljZVx1Yzc0MCBcdWJhODVcdWM4MWNcdWFjMDAgXHViM2Q5XHVjZTU4XHVjNzg0XHVjNzQ0IFx1Yzk5ZFx1YmE4NVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWJlNDRcdWQ2YThcdWM3MjhcdWMxMzFcdWM3NDAgXHVjZTU4XHViYTg1XHVjODAxXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHViMmU0XHVjNzRjIFx1ZDU1OVx1YWUzMCBcdWMyZGNcdWM3OTEgXHVjODA0XHVjNWQwIFx1YWQ1MFx1YzdhY1x1Yjk3YyBcdWJhYThcdWI0NTAgXHVjOWQxXHVkNTQ0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIzYzRcdWI4NWQgXHViNDE4XHViM2M0XHViODVkXHVjNzc0XHViYTc0IFx1YzgwMVx1Yzc0MCBcdWMyMThcdWM3NTggXHVkNTY4XHVjZDk1XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWJhODVcdWM4MWNcdWFjMDAgXHViM2Q5XHVjZTU4XHVjNzg0XHVjNzQ0IFx1Yzk5ZFx1YmE4NVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViM2M0XHViODVkIFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQoMSAmbGU7IFQgJmxlOyAxMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCw8XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjNzg1XHViODI1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJhODVcdWM4MWNcdWM3NTggXHVjMjE4IG4oMSAmbGU7IG4gJmxlOyAyMCwwMDApXHVjNjQwIFx1Yzc3NFx1YmJmOCBcdWM5OWRcdWJhODVcdWI0MWMgXHVkNTY4XHVjZDk1XHVjNzU4IFx1YzIxOCBtKDAgJmxlOyBtICZsZTsgNTAsMDAwKVx1Yzc3NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPm1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwICZxdW90O3M8c3ViPjE8XC9zdWI+XHVjNzc0XHViYTc0IHM8c3ViPjI8XC9zdWI+XHVjNzc0XHViMmU0LiZxdW90OyBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IHM8c3ViPjE8XC9zdWI+XHVhY2ZjIHM8c3ViPjI8XC9zdWI+KDEgJmxlOyBzPHN1Yj4xPFwvc3ViPixzPHN1Yj4yPFwvc3ViPiZuYnNwOyZsZTsgblx1Yzc3NFx1YWNlMCBzPHN1Yj4xJm5ic3A7PFwvc3ViPiZuZTsgczxzdWI+MjxcL3N1Yj4pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1ZDU1YyBcdWM5MDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzcwNFx1YjMwMFx1ZDU1YyBcdWMyMThcdWQ1NTlcdWM3OTAgXHVhZTQwXHVjMTIwXHVjNjAxXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNCBcdWJhODVcdWM4MWNcdWI0ZTRcdWM3NzQgXHViM2Q5XHVjZTU4XHVjNzg0XHVjNzQ0IFx1Yzk5ZFx1YmE4NVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjMGFjXHVjNmE5XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWQ1NjhcdWNkOTVcdWM3NTggXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMi48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM2ODIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQcm92aW5nIEVxdWl2YWxlbmNlcyIsImRlc2NyaXB0aW9uIjoiPHA+Q29uc2lkZXIgdGhlIGZvbGxvd2luZyBleGVyY2lzZSwgZm91bmQgaW4gYSBnZW5lcmljIGxpbmVhciBhbGdlYnJhIHRleHRib29rLjxcL3A+XHJcblxyXG48cD5MZXQgQSBiZSBhbiBuICZ0aW1lczsgbiBtYXRyaXguIFByb3ZlIHRoYXQgdGhlIGZvbGxvd2luZyBzdGF0ZW1lbnRzIGFyZSBlcXVpdmFsZW50OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPihhKSBBIGlzIGludmVydGlibGUuPFwvbGk+XHJcblx0PGxpPihiKSBBeCA9IGIgaGFzIGV4YWN0bHkgb25lIHNvbHV0aW9uIGZvciBldmVyeSBuICZ0aW1lczsgMSBtYXRyaXggYi48XC9saT5cclxuXHQ8bGk+KGMpIEF4ID0gYiBpcyBjb25zaXN0ZW50IGZvciBldmVyeSBuICZ0aW1lczsgMSBtYXRyaXggYi48XC9saT5cclxuXHQ8bGk+KGQpIEF4ID0gMCBoYXMgb25seSB0aGUgdHJpdmlhbCBzb2x1dGlvbiB4ID0gMC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgdHlwaWNhbCB3YXkgdG8gc29sdmUgc3VjaCBhbiBleGVyY2lzZSBpcyB0byBzaG93IGEgc2VyaWVzIG9mIGltcGxpY2F0aW9ucy4gRm9yIGluc3RhbmNlLCBvbmUgY2FuIHByb2NlZWQgYnkgc2hvd2luZyB0aGF0IChhKSBpbXBsaWVzIChiKSwgdGhhdCAoYikgaW1wbGllcyAoYyksIHRoYXQgKGMpIGltcGxpZXMgKGQpLCBhbmQgXHVmYjAxbmFsbHkgdGhhdCAoZCkgaW1wbGllcyAoYSkuIFRoZXNlIGZvdXIgaW1wbGljYXRpb25zIHNob3cgdGhhdCB0aGUgZm91ciBzdGF0ZW1lbnRzIGFyZSBlcXVpdmFsZW50LjxcL3A+XHJcblxyXG48cD5Bbm90aGVyIHdheSB3b3VsZCBiZSB0byBzaG93IHRoYXQgKGEpIGlzIGVxdWl2YWxlbnQgdG8gKGIpIChieSBwcm92aW5nIHRoYXQgKGEpIGltcGxpZXMgKGIpIGFuZCB0aGF0IChiKSBpbXBsaWVzIChhKSksIHRoYXQgKGIpIGlzIGVxdWl2YWxlbnQgdG8gKGMpLCBhbmQgdGhhdCAoYykgaXMgZXF1aXZhbGVudCB0byAoZCkuIEhvd2V2ZXIsIHRoaXMgd2F5IHJlcXVpcmVzIHByb3Zpbmcgc2l4IGltcGxpY2F0aW9ucywgd2hpY2ggaXMgY2xlYXJseSBhIGxvdCBtb3JlIHdvcmsgdGhhbiBqdXN0IHByb3ZpbmcgZm91ciBpbXBsaWNhdGlvbnMhPFwvcD5cclxuXHJcbjxwPkkgaGF2ZSBiZWVuIGdpdmVuIHNvbWUgc2ltaWxhciB0YXNrcywgYW5kIGhhdmUgYWxyZWFkeSBzdGFydGVkIHByb3Zpbmcgc29tZSBpbXBsaWNhdGlvbnMuIE5vdyBJIHdvbmRlciwgaG93IG1hbnkgbW9yZSBpbXBsaWNhdGlvbnMgZG8gSSBoYXZlIHRvIHByb3ZlPyBDYW4geW91IGhlbHAgbWUgZGV0ZXJtaW5lIHRoaXM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgXHVmYjAxcnN0IGxpbmUgb25lIHBvc2l0aXZlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0Y2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0Y2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSBjb250YWluaW5nIHR3byBpbnRlZ2VycyBuICgxICZsZTsgbiAmbGU7IDIwIDAwMCkgYW5kIG0gKDAgJmxlOyBtICZsZTsgNTAgMDAwKTogdGhlIG51bWJlciBvZiBzdGF0ZW1lbnRzIGFuZCB0aGUgbnVtYmVyIG9mIGltcGxpY2F0aW9ucyB0aGF0IGhhdmUgYWxyZWFkeSBiZWVuIHByb3ZlZC48XC9saT5cclxuXHQ8bGk+bSBsaW5lcyB3aXRoIHR3byBpbnRlZ2VycyBzPHN1Yj4xPFwvc3ViPiBhbmQgczxzdWI+MjxcL3N1Yj4gKDEgJmxlOyBzPHN1Yj4xPFwvc3ViPiwgczxzdWI+MjxcL3N1Yj4gJmxlOyBuIGFuZCBzPHN1Yj4xPFwvc3ViPiAmbmU7IHM8c3ViPjI8XC9zdWI+KSBlYWNoLCBpbmRpY2F0aW5nIHRoYXQgaXQgaGFzIGJlZW4gcHJvdmVkIHRoYXQgc3RhdGVtZW50IHM8c3ViPjE8XC9zdWI+IGltcGxpZXMgc3RhdGVtZW50IHM8c3ViPjI8XC9zdWI+LjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggdGhlIG1pbmltdW0gbnVtYmVyIG9mIGFkZGl0aW9uYWwgaW1wbGljYXRpb25zIHRoYXQgbmVlZCB0byBiZSBwcm92ZWQgaW4gb3JkZXIgdG8gcHJvdmUgdGhhdCBhbGwgc3RhdGVtZW50cyBhcmUgZXF1aXZhbGVudC48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2008 B번