문제
$N$개의 정점과 $M$개의 간선을 가진 무향 그래프 $G$가 주어진다. 시간 $T=1$일 때, $G$에서 정해진 $K$개의 정점을 지운다. $T=t\ (1 < t)$일 때는 $T=t-1$에서 지워진 정점과 이웃하였던 정점들을 지운다. 이때 $G$에 사이클이 존재하지 않는 최초의 시간 $T=C$를 구하는 프로그램을 작성하여라.
처음 주어지는 그래프 $G$는 모든 정점이 연결된 연결 그래프이며, 사이클이 존재한다. 또한 정점이 삭제되면 해당 정점과 연결된 간선도 함께 없어진다. 자기 자신과 연결된 간선은 주어지지 않으며, 중복된 간선이 주어질 수 있다.
출력
첫 번째 줄에 $T=C$에서 정점을 지우고 처음으로 사이클이 존재하지 않게 되었을 때의 시간 $C$를 출력한다.
노트
$G$의 사이클은 $G$의 부분그래프 중 비어있지 않고 연결되어 있으며, 모든 정점의 차수가 2ドル$인 그래프를 의미한다.
W3sicHJvYmxlbV9pZCI6IjMwODcwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMGFjXHVjNzc0XHVkMDc0IFx1YzVjNlx1YjI5NCBcdWFkZjhcdWI3OThcdWQ1MDQgXHViOWNjXHViNGU0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD4kTiRcdWFjMWNcdWM3NTggXHVjODE1XHVjODEwXHVhY2ZjICRNJFx1YWMxY1x1Yzc1OCBcdWFjMDRcdWMxMjBcdWM3NDQgXHVhYzAwXHVjOWM0IFx1YmIzNFx1ZDVhNSBcdWFkZjhcdWI3OThcdWQ1MDQgJEckXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMmRjXHVhYzA0ICRUPTEkXHVjNzdjIFx1YjU0YywgJEckXHVjNWQwXHVjMTFjIFx1YzgxNVx1ZDU3NFx1YzljNCAkSyRcdWFjMWNcdWM3NTggXHVjODE1XHVjODEwXHVjNzQ0IFx1YzljMFx1YzZiNFx1YjJlNC4gJFQ9dFxcICgxICZsdDsgdCkkXHVjNzdjIFx1YjU0Y1x1YjI5NCAkVD10LTEkXHVjNWQwXHVjMTFjIFx1YzljMFx1YzZjY1x1YzljNCBcdWM4MTVcdWM4MTBcdWFjZmMgXHVjNzc0XHVjNmMzXHVkNTU4XHVjNjAwXHViMzU4IFx1YzgxNVx1YzgxMFx1YjRlNFx1Yzc0NCBcdWM5YzBcdWM2YjRcdWIyZTQuIFx1Yzc3NFx1YjU0YyAkRyRcdWM1ZDAgXHVjMGFjXHVjNzc0XHVkMDc0XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjZDVjXHVjZDA4XHVjNzU4IFx1YzJkY1x1YWMwNCAkVD1DJFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG5cclxuPHA+XHVjYzk4XHVjNzRjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWFkZjhcdWI3OThcdWQ1MDQgJEckXHViMjk0IFx1YmFhOFx1YjRlMCBcdWM4MTVcdWM4MTBcdWM3NzQgXHVjNWYwXHVhY2IwXHViNDFjIFx1YzVmMFx1YWNiMCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NzRcdWJhNzAsIFx1YzBhY1x1Yzc3NFx1ZDA3NFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuIFx1YjYxMFx1ZDU1YyBcdWM4MTVcdWM4MTBcdWM3NzQgXHVjMGFkXHVjODFjXHViNDE4XHViYTc0IFx1ZDU3NFx1YjJmOSBcdWM4MTVcdWM4MTBcdWFjZmMgXHVjNWYwXHVhY2IwXHViNDFjIFx1YWMwNFx1YzEyMFx1YjNjNCBcdWQ1NjhcdWFlZDggXHVjNWM2XHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3OTBcdWFlMzAgXHVjNzkwXHVjMmUwXHVhY2ZjIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWFjMDRcdWMxMjBcdWM3NDAgXHVjOGZjXHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3MCwgXHVjOTExXHViY2Y1XHViNDFjIFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWRmOFx1Yjc5OFx1ZDUwNCAkRyRcdWM3NTggXHVjODE1XHVjODEwXHVjNzU4IFx1YzIxOCAkTiRcdWFjZmMgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YzIxOCAkTSQsIFx1YzJkY1x1YWMwNCAkVD0xJFx1Yzc3YyBcdWI1NGMgXHVjMGFkXHVjODFjXHVkNTU4XHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWMyMTggJEskXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDJcXGxlIE5cXGxlIE1cXGxlIDIwMFxcLCAwMDA7JCAkMVxcbGUgS1xcbGUgTikkPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwICRNJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWM4MTVcdWJjZjQgJHUsIHYkXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWIyOTQgJHUkXHViYzg4IFx1YzgxNVx1YzgxMFx1YWNmYyAkdiRcdWJjODggXHVjODE1XHVjODEwXHVjNzc0IFx1YWMwNFx1YzEyMFx1YzczY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzRjXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gJCgxXFxsZSB1LHZcXGxlIE47JCAkdSBcXG5lIHYpJDxcL3A+XHJcblxyXG48cD5cdWFkZjggXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCAkVD0xJFx1Yzc3YyBcdWI1NGMgXHVjMGFkXHVjODFjXHVkNTU4XHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWJjODhcdWQ2MzggJEskXHVhYzFjXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwICRUPUMkXHVjNWQwXHVjMTFjIFx1YzgxNVx1YzgxMFx1Yzc0NCBcdWM5YzBcdWM2YjBcdWFjZTAgXHVjYzk4XHVjNzRjXHVjNzNjXHViODVjIFx1YzBhY1x1Yzc3NFx1ZDA3NFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHVhYzhjIFx1YjQxOFx1YzVjOFx1Yzc0NCBcdWI1NGNcdWM3NTggXHVjMmRjXHVhYzA0ICRDJFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPiRHJFx1Yzc1OCBcdWMwYWNcdWM3NzRcdWQwNzRcdWM3NDAgJEckXHVjNzU4IFx1YmQ4MFx1YmQ4NFx1YWRmOFx1Yjc5OFx1ZDUwNCBcdWM5MTEgXHViZTQ0XHVjNWI0XHVjNzg4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjODEwXHVjNzU4IFx1Y2MyOFx1YzIxOFx1YWMwMCAkMiRcdWM3NzggXHVhZGY4XHViNzk4XHVkNTA0XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMwODcwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTWFraW5nIEN5Y2xlbGVzcyBHcmFwaHMiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gYW4gdW5kaXJlY3RlZCBncmFwaCAkRyQgY29uc2lzdGluZyBvZiAkTiQgbm9kZXMgYW5kICRNJCBlZGdlcy4gQXQgdGltZSAkVD0xJCwgcmVtb3ZlICRLJCBnaXZlbiBub2RlcyBmcm9tICRHJC4gV2hlbiAkVD10XFwgKDEmbmJzcDsmbHQ7IHQpJCwgcmVtb3ZlIG5vZGVzIHRoYXQgd2VyZSBhZGphY2VudCB0byBub2RlcyByZW1vdmVkIGF0ICRUPXQtMSQuIFdyaXRlIGEgcHJvZ3JhbSB0aGF0IGZpbmRzIHRoZSBmYXN0ZXN0IHRpbWUgJFQ9QyQgd2hlbiB0aGVyZSBpcyBubyBjeWNsZSBpbiAkRyQuPFwvcD5cclxuXHJcbjxwPkl0IGlzIGd1YXJhbnRlZWQgdGhhdCAkRyQgaXMgaW5pdGlhbGx5IGEgY29ubmVjdGVkIGdyYXBoIGFuZCBjb250YWlucyBhdCBsZWFzdCBvbmUgY3ljbGUuIEluIGFkZGl0aW9uLCB0aGUgcmVtb3ZhbCBvZiBhIG5vZGUgcmVtb3ZlcyBhbGwgY29ubmVjdGVkIGVkZ2VzIGZyb20gaXQgYXMgd2VsbC4gVGhlcmUgaXMgbm8gZWRnZSB0aGF0IGNvbm5lY3RzIGEgbm9kZSB0byBpdHNlbGYuIFRoZSBzYW1lIGVkZ2UgbWF5IGJlIGdpdmVuIG11bHRpcGxlIHRpbWVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzICROJCwgJE0kLCBhbmQgJEskLCBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIG5vZGVzIGluICRHJCwgdGhlIG51bWJlciBvZiBlZGdlcywgYW5kIHRoZSBudW1iZXIgb2Ygbm9kZXMgcmVtb3ZlZCB3aGVuICRUPTEkLCByZXNwZWN0aXZlbHkuICQoMlxcbGUgTlxcbGUgTVxcbGUgMjAwXFwsIDAwMDskICQxXFxsZSBLXFxsZSBOKSQ8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCAkTSQgbGluZXMgb2YgaW5wdXQgY29udGFpbnMgdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyAkdSQgYW5kICR2JCwgZGVub3RpbmcgdGhhdCB0aGVyZSBpcyBhbiBlZGdlIGNvbm5lY3Rpbmcgbm9kZSAkdSQgYW5kIG5vZGUgJHYkLiAkKDFcXGxlIHUsIHZcXGxlIE47JCAkdSBcXG5lIHYpJDxcL3A+XHJcblxyXG48cD5UaGUgbGFzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zICRLJCBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMsIGRlbm90aW5nIHRoZSBub2RlcyByZW1vdmVkIHdoZW4gJFQ9MSQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIGEgc2luZ2xlIGludGVnZXIgJEMkLCB3aGVyZSAkVD1DJCBpcyB0aGUgZmFzdGVzdCB0aW1lIGZvciBubyBjeWNsZSBleGlzdHMgaW4gdGhlIGdyYXBoLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5BIGN5Y2xlIGluICRHJCByZWZlcnMgdG8gYSBub24tZW1wdHksIGNvbm5lY3RlZCBzdWJncmFwaCBvZiAkRyQgd2hlcmUgdGhlIGRlZ3JlZSBvZiBldmVyeSBub2RlIGlzICQyJC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=