문제
드래곤 나라에는 N개의 도시와 M개의 도로가 있다. 도시들은 1번 부터 N번까지 번호가 붙어 있으며 각 도로는 두개의 도시를 연결한다. 이 N개의 도시에는 전체 합이 K마리인 D1, D2, ... DK드래곤이 살고 있다. 도시 Ci에 살고 있는 드래곤 Di는 처음에 Si의 머리를 가지고 있다. 드래곤이 살아있는 동안 매 분 Ni개의 새로운 머리가 자란다. 드래곤은 하나 이상의 머리가 남아 있으면 생존할 수 있다.
우린 드래곤을 처치하기 위해 워리어를 고용할것이다. 매 분마다 각 워리어는 인접한 도시로 이동하거나 자신이 머물고 있는 도시의 드래곤의 머리 하나를 자를 수 있다. 우리는 워리어가 매 분마다 취할 전략을 정할 수 있다. 또한 우리는 각 워리어가 머무는 최초 도시를 지정할 수 있다.
유한한 시간에 모든 드래곤을 죽이기 위해 필요한 최소 워리어 수를 구하라.
출력
각 테스트 케이스에 대해 결과는 모든 드래곤을 죽일 수 잇는 최소 워리어 수를 출력해야한다.
W3sicHJvYmxlbV9pZCI6IjEwNjA1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViNGRjXHViNzk4XHVhY2U0IFx1YzhmZFx1Yzc3NFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHViNGRjXHViNzk4XHVhY2U0IFx1YjA5OFx1Yjc3Y1x1YzVkMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1YzY0MCBNXHVhYzFjXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YjNjNFx1YzJkY1x1YjRlNFx1Yzc0MCAxXHViYzg4IFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwIFx1YWMwMSBcdWIzYzRcdWI4NWNcdWIyOTQgXHViNDUwXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBOXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1YzVkMFx1YjI5NCBcdWM4MDRcdWNjYjQgXHVkNTY5XHVjNzc0IEtcdWI5YzhcdWI5YWNcdWM3NzggRDxzdWI+MTxcL3N1Yj4sIEQ8c3ViPjI8XC9zdWI+LCAuLi4gRDxzdWI+SzxcL3N1Yj5cdWI0ZGNcdWI3OThcdWFjZTRcdWM3NzQgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViM2M0XHVjMmRjIEM8c3ViPmk8XC9zdWI+XHVjNWQwIFx1YzBiNFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViNGRjXHViNzk4XHVhY2U0IEQ8c3ViPmk8XC9zdWI+XHViMjk0IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBTPHN1Yj5pPFwvc3ViPlx1Yzc1OCBcdWJhMzhcdWI5YWNcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViNGRjXHViNzk4XHVhY2U0XHVjNzc0IFx1YzBiNFx1YzU0NFx1Yzc4OFx1YjI5NCBcdWIzZDlcdWM1NDggXHViOWU0IFx1YmQ4NCBOPHN1Yj5pPFwvc3ViPlx1YWMxY1x1Yzc1OCBcdWMwYzhcdWI4NWNcdWM2YjQgXHViYTM4XHViOWFjXHVhYzAwIFx1Yzc5MFx1Yjc4MFx1YjJlNC4gXHViNGRjXHViNzk4XHVhY2U0XHVjNzQwIFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzFcdWM3NTggXHViYTM4XHViOWFjXHVhYzAwIFx1YjBhOFx1YzU0NCBcdWM3ODhcdWM3M2NcdWJhNzQgXHVjMGRkXHVjODc0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZiMFx1YjliMCBcdWI0ZGNcdWI3OThcdWFjZTRcdWM3NDQgXHVjYzk4XHVjZTU4XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM2Y2NcdWI5YWNcdWM1YjRcdWI5N2MgXHVhY2UwXHVjNmE5XHVkNTYwXHVhYzgzXHVjNzc0XHViMmU0LiBcdWI5ZTQgXHViZDg0XHViOWM4XHViMmU0IFx1YWMwMSBcdWM2Y2NcdWI5YWNcdWM1YjRcdWIyOTQgXHVjNzc4XHVjODExXHVkNTVjIFx1YjNjNFx1YzJkY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjNzBcdWIwOTggXHVjNzkwXHVjMmUwXHVjNzc0IFx1YmEzOFx1YmIzY1x1YWNlMCBcdWM3ODhcdWIyOTQgXHViM2M0XHVjMmRjXHVjNzU4IFx1YjRkY1x1Yjc5OFx1YWNlNFx1Yzc1OCBcdWJhMzhcdWI5YWMgXHVkNTU4XHViMDk4XHViOTdjIFx1Yzc5MFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM2YjBcdWI5YWNcdWIyOTQgXHVjNmNjXHViOWFjXHVjNWI0XHVhYzAwIFx1YjllNCBcdWJkODRcdWI5YzhcdWIyZTQgXHVjZGU4XHVkNTYwIFx1YzgwNFx1YjdiNVx1Yzc0NCBcdWM4MTVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNjEwXHVkNTVjIFx1YzZiMFx1YjlhY1x1YjI5NCBcdWFjMDEgXHVjNmNjXHViOWFjXHVjNWI0XHVhYzAwIFx1YmEzOFx1YmIzNFx1YjI5NCBcdWNkNWNcdWNkMDggXHViM2M0XHVjMmRjXHViOTdjIFx1YzljMFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MjBcdWQ1NWNcdWQ1NWMgXHVjMmRjXHVhYzA0XHVjNWQwIFx1YmFhOFx1YjRlMCBcdWI0ZGNcdWI3OThcdWFjZTRcdWM3NDQgXHVjOGZkXHVjNzc0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YzZjY1x1YjlhY1x1YzViNCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTM4XHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBOLCBNLCBLICgxJm5ic3A7JmxlOyBOICZsZTsgMzAwLCAwICZsZTsgTSAmbGU7IE4oTi0xKSwgMSAmbGU7IEsgJmxlOyAxMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOCBcdWQ2YzQgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjNjNFx1YzJkYyBhXHVjNjQwIGIgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YzVmMFx1YWNiMFx1Yzc0NCBcdWFjMDBcdWI5YWNcdWQwYTRcdWIyOTQgXHViNDUwXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBhLCBiICgxICZsZTsgYSAmbmU7IGIgJmxlOyBOKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1ZDZjNCBLXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIEtcdWFjMWMgXHVjOTA0XHVjNzU4IGlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjRkY1x1Yjc5OFx1YWNlNCBEPHN1Yj5pPFwvc3ViPlx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVhYzEyIEM8c3ViPmk8XC9zdWI+LCBTPHN1Yj5pPFwvc3ViPiwgTjxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBDPHN1Yj5pPFwvc3ViPiAmbGU7IE4sIDEgJmxlOyBTPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD41PFwvc3VwPiwgMCAmbGU7IE48c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjU8XC9zdXA+KVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIDAgMCAwXHVjNzc0IFx1Yzc4NVx1YjgyNVx1YjQxOFx1YmE3NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1Yzg4NVx1YjhjY1x1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVhY2IwXHVhY2ZjXHViMjk0IFx1YmFhOFx1YjRlMCBcdWI0ZGNcdWI3OThcdWFjZTRcdWM3NDQgXHVjOGZkXHVjNzdjIFx1YzIxOCBcdWM3ODdcdWIyOTQgXHVjZDVjXHVjMThjIFx1YzZjY1x1YjlhY1x1YzViNCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjEwNjA1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRHJhZ29ucyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgYXJlIE4gY2l0aWVzIGFuZCBNIHJvYWRzIGluIERyYWdvbnMgQ291bnRyeS4gQ2l0aWVzIGFyZSBudW1iZXJlZCAxIHRocm91Z2ggTiwgYW5kIGVhY2ggcm9hZCBjb25uZWN0cyBleGFjdGx5IHR3byBjaXRpZXMuIFRoZXJlIGFyZSB0b3RhbGx5IEsgZHJhZ29ucyBEMSwgRDIsIC4gLiAuICwgREsgaW4gdGhlc2UgTiBjaXRpZXMuIERyYWdvbiBEaSBsaXZlcyBpbiBjaXR5IENpIGFuZCBoYXMgaW5pdGlhbGx5IFNpIGhlYWRzLiBJdCBncm93cyBOaSBuZXcgaGVhZHMgZXZlcnkgbWludXRlIHdoaWxlIGFsaXZlISBBIGRyYWdvbiBpcyBhbGl2ZSBpZiBpdCBoYXMgcG9zaXRpdmUgbnVtYmVyIG9mIGhlYWRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5XZSB3YW50IHRvIGhpcmUgYSBudW1iZXIgb2Ygd2FycmlvcnMgdG8ga2lsbCBhbGwgZHJhZ29ucy4gV2Ugc3BlY2lmeSB0aGUgaW5pdGlhbCBjaXR5IG9mIGVhY2ggd2Fycmlvci4gVGhlbiBvbiBlYWNoIG1pbnV0ZSwgZWFjaCB3YXJyaW9yIGNhbiBlaXRoZXIgZ28gdGhyb3VnaCBhIHJvYWQgZnJvbSBoaXMgY3VycmVudCBjaXR5IHRvIGFuIGFkamFjZW50IGNpdHksIG9yIHNlbGVjdCBhbiBhbGl2ZSBkcmFnb24gaW4gaGlzIGN1cnJlbnQgY2l0eSBhbmQgY3V0IG9mZiBvbmUgb2YgaXRzIGhlYWRzLiBXZSBjYW4gc3BlY2lmeSB0aGUgc3RyYXRlZ3kgb2YgZWFjaCB3YXJyaW9yIG9uIGVhY2ggbWludXRlLCBhbmQgYWZ0ZXIgdGhleSBhcmUgZG9uZSwgYW55IGFsaXZlIGRyYWdvbiBEaSB3aWxsIGdyb3cgaXRzIE5pIG5ldyBoZWFkcy48XC9wPlxyXG5cclxuPHA+V2Ugd2FudCB0byBmaW5kIHRoZSBtaW5pbXVtIG51bWJlciBvZiB3YXJyaW9ycyB3aXRoIHdoaWNoIGFsbCBkcmFnb25zIGNhbiBiZSBraWxsZWQgaW4gYSBmaW5pdGUgYW1vdW50IG9mIHRpbWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGVyZSBhcmUgbXVsdGlwbGUgdGVzdCBjYXNlcyBpbiB0aGUgaW5wdXQuIEZvciBlYWNoIHRlc3QgY2FzZSwgdGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIE4sIE0gYW5kIEsgKDEgXHUyYTdkIE4gXHUyYTdkIDMwMCwgMCBcdTJhN2QgTSBcdTJhN2QgTihOICZtaW51czsgMSlcLzIsIGFuZCAxIFx1MmE3ZCBLIFx1MmE3ZCAxMDAwKS4gRWFjaCBvZiB0aGUgbmV4dCBNIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBhIGFuZCBiICgxIFx1MmE3ZCBhICZuZTsmbmJzcDtiIFx1MmE3ZCBOKSBpbmRpY2F0aW5nIGEgcm9hZCBiZXR3ZWVuIGNpdGllcyBhIGFuZCBiLiBUaGUgaS10aCBsaW5lIG9mIHRoZSBuZXh0IEsgbGluZXMgZGVzY3JpYmVzIGRyYWdvbiBEaSB3aXRoIHRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBDaSwgU2kgYW5kIE5pICgxIFx1MmE3ZCBDaSBcdTJhN2QgTiwgMSBcdTJhN2QgU2kgXHUyYTdkIDEwPHN1cD41PFwvc3VwPiwgMCBcdTJhN2QgTmkgXHUyYTdkIDEwPHN1cD41PFwvc3VwPikuIFRoZSBpbnB1dCB0ZXJtaW5hdGVzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgMCAwIDAgd2hpY2ggc2hvdWxkIG5vdCBiZSBwcm9jZXNzZWQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgYSBsaW5lIGNvbnRhaW5pbmcgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHdhcnJpb3JzIHdobyBjYW4gZXZlbnR1YWxseSBraWxsIGFsbCBkcmFnb25zLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=