시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1092 304 200 26.631%

문제

도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러뜨릴 수 있다. 그러나, 가끔씩 도미노가 다른 블록을 넘어뜨리지 못하게 배치되어 있다면, 우리는 다음 블록을 수동으로 넘어뜨려야 한다.

이제 각 도미노 블록의 배치가 주어졌을 때, 모든 블록을 넘어뜨리기 위해 손으로 넘어뜨려야 하는 블록 개수의 최소값을 구하자.

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 N, M이 주어지며 두 수는 100,000을 넘지 않는다. N은 도미노의 개수를, M은 관계의 개수를 나타낸다. 도미노 블록의 번호는 1과 N 사이의 정수다. 다음 M개의 줄에는 각각 두 정수 x, y가 주어지는데, 이는 x번 블록이 넘어지면 y번 블록도 넘어짐을 뜻한다.

출력

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 정답은 손으로 넘어뜨려야 하는 최소의 도미노 블록 개수이다.

예제 입력 1

1
3 2
1 2
2 3

예제 출력 1

1
W3sicHJvYmxlbV9pZCI6IjQxOTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzYzRcdWJiZjhcdWIxNzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjNjNFx1YmJmOFx1YjE3OFx1YjI5NCBcdWM3YWNcdWJjMGNcdWIyZTQuIFx1YjNjNFx1YmJmOFx1YjE3OCBcdWJlMTRcdWI4NWRcdWM3NDQmbmJzcDtcdWM3N2NcdWI4MmNcdWI4NWMgXHVhZTM4XHVhYzhjIFx1YjI5OFx1YzViNFx1YzEzOFx1YzZiNCBcdWI0YTQmbmJzcDtcdWJlMTRcdWI4NWQgXHVkNTU4XHViMDk4XHViOTdjIFx1YjExOFx1YzViNFx1YjcyOFx1YjlhY1x1YmE3NCBcdWFkZjggXHViZTE0XHViODVkXHVjNzc0IFx1YjExOFx1YzViNFx1YzljMFx1YmE3MCBcdWIyZTRcdWM3NGMgXHViZTE0XHViODVkXHVjNzQ0IFx1YjExOFx1YzViNFx1YjcyOFx1YjlhY1x1YjI5NCBcdWM3N2NcdWM3NzQgXHViYzE4XHViY2Y1XHViNDE4XHVjNWI0IFx1Yzc3Y1x1YjgyY1x1Yjg1YyBcdWIyOThcdWM1YjRcdWMxMjAgXHViZTE0XHViODVkXHViNGU0XHVjNzQ0Jm5ic3A7XHVjNWYwXHVjMWM0XHVjODAxXHVjNzNjXHViODVjIFx1YmFhOFx1YjQ1MCBcdWM0ZjBcdWI3ZWNcdWI3MjhcdWI5YjQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViN2VjXHViMDk4LCBcdWFjMDBcdWIwNTRcdWM1MjkgXHViM2M0XHViYmY4XHViMTc4XHVhYzAwIFx1YjJlNFx1Yjk3OCBcdWJlMTRcdWI4NWRcdWM3NDQgXHViMTE4XHVjNWI0XHViNzI4XHViOWFjXHVjOWMwIFx1YmFiYlx1ZDU1OFx1YWM4YyBcdWJjMzBcdWNlNThcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0XHViYTc0LCBcdWM2YjBcdWI5YWNcdWIyOTQgXHViMmU0XHVjNzRjIFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWMyMThcdWIzZDlcdWM3M2NcdWI4NWMgXHViMTE4XHVjNWI0XHViNzI4XHViODI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjODFjIFx1YWMwMSBcdWIzYzRcdWJiZjhcdWIxNzggXHViZTE0XHViODVkXHVjNzU4IFx1YmMzMFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHViZTE0XHViODVkXHVjNzQ0IFx1YjExOFx1YzViNFx1YjcyOFx1YjlhY1x1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjMTkwXHVjNzNjXHViODVjIFx1YjExOFx1YzViNFx1YjcyOFx1YjgyNFx1YzU3YyBcdWQ1NThcdWIyOTQgXHViZTE0XHViODVkIFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4IE4sIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwIFx1YjQ1MCBcdWMyMThcdWIyOTQgMTAwLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBOXHVjNzQwIFx1YjNjNFx1YmJmOFx1YjE3OFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MsIE1cdWM3NDAgXHVhZDAwXHVhY2M0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YjNjNFx1YmJmOFx1YjE3OCBcdWJlMTRcdWI4NWRcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDFcdWFjZmMgTiBcdWMwYWNcdWM3NzRcdWM3NTggXHVjODE1XHVjMjE4XHViMmU0LiBcdWIyZTRcdWM3NGMgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxXHVhYzAxIFx1YjQ1MCBcdWM4MTVcdWMyMTggeCwgeVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAsIFx1Yzc3NFx1YjI5NCB4XHViYzg4IFx1YmUxNFx1Yjg1ZFx1Yzc3NCBcdWIxMThcdWM1YjRcdWM5YzBcdWJhNzQgeVx1YmM4OCBcdWJlMTRcdWI4NWRcdWIzYzQgXHViMTE4XHVjNWI0XHVjOWQwXHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOCBcdWQ1NThcdWIwOThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM4MTVcdWIyZjVcdWM3NDAmbmJzcDtcdWMxOTBcdWM3M2NcdWI4NWMmbmJzcDtcdWIxMThcdWM1YjRcdWI3MjhcdWI4MjRcdWM1N2MgXHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1Yzc1OCBcdWIzYzRcdWJiZjhcdWIxNzggXHViZTE0XHViODVkIFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MTk2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRG9taW5vcyIsImRlc2NyaXB0aW9uIjoiPHA+RG9taW5vcyBhcmUgbG90cyBvZiBmdW4uIENoaWxkcmVuIGxpa2UgdG8gc3RhbmQgdGhlIHRpbGVzIG9uIHRoZWlyIHNpZGUgaW4gbG9uZyBsaW5lcy4gV2hlbiBvbmUgZG9taW5vIGZhbGxzLCBpdCBrbm9ja3MgZG93biB0aGUgbmV4dCBvbmUsIHdoaWNoIGtub2NrcyBkb3duIHRoZSBvbmUgYWZ0ZXIgdGhhdCwgYWxsIHRoZSB3YXkgZG93biB0aGUgbGluZS4gSG93ZXZlciwgc29tZXRpbWVzIGEgZG9taW5vIGZhaWxzIHRvIGtub2NrIHRoZSBuZXh0IG9uZSBkb3duLiBJbiB0aGF0IGNhc2UsIHdlIGhhdmUgdG8ga25vY2sgaXQgZG93biBieSBoYW5kIHRvIGdldCB0aGUgZG9taW5vcyBmYWxsaW5nIGFnYWluLjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gZGV0ZXJtaW5lLCBnaXZlbiB0aGUgbGF5b3V0IG9mIHNvbWUgZG9taW5vIHRpbGVzLCB0aGUgbWluaW11bSBudW1iZXIgb2YgZG9taW5vcyB0aGF0IG11c3QgYmUga25vY2tlZCBkb3duIGJ5IGhhbmQgaW4gb3JkZXIgZm9yIGFsbCBvZiB0aGUgZG9taW5vcyB0byBmYWxsLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgb25lIGludGVnZXIgc3BlY2lmeWluZyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgdG8gZm9sbG93LiBFYWNoIHRlc3QgY2FzZSBiZWdpbnMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlcnMsIGVhY2ggbm8gbGFyZ2VyIHRoYW4gMTAwIDAwMC4gVGhlIGZpcnN0IGludGVnZXIgbiBpcyB0aGUgbnVtYmVyIG9mIGRvbWlubyB0aWxlcyBhbmQgdGhlIHNlY29uZCBpbnRlZ2VyIG0gaXMgdGhlIG51bWJlciBvZiBsaW5lcyB0byBmb2xsb3cgaW4gdGhlIHRlc3QgY2FzZS4gVGhlIGRvbWlubyB0aWxlcyBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIG4uIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgeCBhbmQgeSBpbmRpY2F0aW5nIHRoYXQgaWYgZG9taW5vIG51bWJlciB4IGZhbGxzLCBpdCB3aWxsIGNhdXNlIGRvbWlubyBudW1iZXIgeSB0byBmYWxsIGFzIHdlbGwuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgYSBsaW5lIGNvbnRhaW5pbmcgb25lIGludGVnZXIsIHRoZSBtaW5pbXVtIG51bWJlciBvZiBkb21pbm9zIHRoYXQgbXVzdCBiZSBrbm9ja2VkIG92ZXIgYnkgaGFuZCBpbiBvcmRlciBmb3IgYWxsIHRoZSBkb21pbm9zIHRvIGZhbGwuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d