문제
히바이는 새로운 예술 작품을 만들기로 했다. 모든 예술 작품에 의미를 담는 히바이는 다음과 같은 생각을 담아 예술 작품을 만들기로 했다.
- 이번 예술 작품은 “모든 것에는 순서가 있고 흐름이 있다”는 것을 담는 방향 비순환 그래프를 기반으로 한다.
- 또한, “모든 것에는 저마다의 색이 있다”는 점을 담아 그래프의 각 정점에 색깔을 칠할 것이다.
- 여기에, “세상에는 어떻게 보아도 새로운 것들이 넘쳐난다”는 점을 담아 그래프 위의 임의의 경로에 대해 해당하는 경로 위의 모든 정점의 색깔을 다르게 칠할 것이다.
- 마지막으로, “그럼에도 넓게 보면 생각보다 비슷한 것들은 많다”는 점을 담아 사용하는 색깔의 개수를 최소화할 것이다.
방향 비순환 그래프가 주어질 때, 히바이가 위와 같은 생각을 담아 정점을 칠한다면 최소 몇 개의 색깔을 사용해야 하는지 구해보자.
출력
첫째 줄에 히바이가 최소 몇 개의 색깔을 사용해야 하는지 출력한다.
W3sicHJvYmxlbV9pZCI6IjM0MTMzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiW0FdIEFydGlzdGljIEdyYXBoIENvbG9yaW5nIFRhc2siLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDc4OFx1YmMxNFx1Yzc3NFx1YjI5NCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjNjA4XHVjMjIwIFx1Yzc5MVx1ZDQ4OFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjNjA4XHVjMjIwIFx1Yzc5MVx1ZDQ4OFx1YzVkMCBcdWM3NThcdWJiZjhcdWI5N2MgXHViMmY0XHViMjk0IFx1ZDc4OFx1YmMxNFx1Yzc3NFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzBkZFx1YWMwMVx1Yzc0NCBcdWIyZjRcdWM1NDQgXHVjNjA4XHVjMjIwIFx1Yzc5MVx1ZDQ4OFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1Yzc3NFx1YmM4OCBcdWM2MDhcdWMyMjAgXHVjNzkxXHVkNDg4XHVjNzQwICZsZHF1bztcdWJhYThcdWI0ZTAgXHVhYzgzXHVjNWQwXHViMjk0IFx1YzIxY1x1YzExY1x1YWMwMCBcdWM3ODhcdWFjZTAgXHVkNzUwXHViOTg0XHVjNzc0IFx1Yzc4OFx1YjJlNCZyZHF1bztcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YjJmNFx1YjI5NCBcdWJjMjlcdWQ1YTUgXHViZTQ0XHVjMjFjXHVkNjU4IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yjk3YyBcdWFlMzBcdWJjMThcdWM3M2NcdWI4NWMgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI2MTBcdWQ1NWMsICZsZHF1bztcdWJhYThcdWI0ZTAgXHVhYzgzXHVjNWQwXHViMjk0IFx1YzgwMFx1YjljOFx1YjJlNFx1Yzc1OCBcdWMwYzlcdWM3NzQgXHVjNzg4XHViMmU0JnJkcXVvO1x1YjI5NCBcdWM4MTBcdWM3NDQgXHViMmY0XHVjNTQ0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWFjMDEgXHVjODE1XHVjODEwXHVjNWQwIFx1YzBjOVx1YWU1NFx1Yzc0NCBcdWNlNjBcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM1ZWNcdWFlMzBcdWM1ZDAsICZsZHF1bztcdWMxMzhcdWMwYzFcdWM1ZDBcdWIyOTQgXHVjNWI0XHViNWJiXHVhYzhjIFx1YmNmNFx1YzU0NFx1YjNjNCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVhYzgzXHViNGU0XHVjNzc0IFx1YjExOFx1Y2NkMFx1YjA5Y1x1YjJlNCZyZHF1bztcdWIyOTQgXHVjODEwXHVjNzQ0IFx1YjJmNFx1YzU0NCBcdWFkZjhcdWI3OThcdWQ1MDQgXHVjNzA0XHVjNzU4IFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWFjYmRcdWI4NWNcdWM1ZDAgXHViMzAwXHVkNTc0IFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWI4NWMgXHVjNzA0XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM4MTVcdWM4MTBcdWM3NTggXHVjMGM5XHVhZTU0XHVjNzQ0IFx1YjJlNFx1Yjk3NFx1YWM4YyBcdWNlNjBcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMsICZsZHF1bztcdWFkZjhcdWI3ZmNcdWM1ZDBcdWIzYzQgXHViMTEzXHVhYzhjIFx1YmNmNFx1YmE3NCBcdWMwZGRcdWFjMDFcdWJjZjRcdWIyZTQgXHViZTQ0XHVjMmI3XHVkNTVjIFx1YWM4M1x1YjRlNFx1Yzc0MCBcdWI5Y2VcdWIyZTQmcmRxdW87XHViMjk0IFx1YzgxMFx1Yzc0NCBcdWIyZjRcdWM1NDQgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0IFx1YzBjOVx1YWU1NFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDVjXHVjMThjXHVkNjU0XHVkNTYwIFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWJjMjlcdWQ1YTUgXHViZTQ0XHVjMjFjXHVkNjU4IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBcdWQ3ODhcdWJjMTRcdWM3NzRcdWFjMDAgXHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWMwZGRcdWFjMDFcdWM3NDQgXHViMmY0XHVjNTQ0IFx1YzgxNVx1YzgxMFx1Yzc0NCBcdWNlNjBcdWQ1NWNcdWIyZTRcdWJhNzQgXHVjZDVjXHVjMThjIFx1YmE4NyBcdWFjMWNcdWM3NTggXHVjMGM5XHVhZTU0XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMjlcdWQ1YTUgXHViZTQ0XHVjMjFjXHVkNjU4IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWM4MTVcdWM4MTAgXHVhYzFjXHVjMjE4ICROJFx1YWNmYyBcdWFjMDRcdWMxMjAgXHVhYzFjXHVjMjE4ICRNJFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxXFxsZSBOXFxsZSAyMDBcXCwgMDAwOyQgJDBcXGxlIE1cXGxlIDMwMFxcLCAwMDApJDxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwICRNJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YjQ1MCBcdWM4MTVcdWMyMTggJHYkLCAkdyRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjI5NCAkdiRcdWJjODggXHVjODE1XHVjODEwXHVjNzQ0IFx1YzJkY1x1Yzc5MVx1YzgxMFx1YzczY1x1Yjg1YyBcdWQ1NThcdWFjZTAsICR3JFx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3NDQgXHViMDVkXHVjODEwXHVjNzNjXHViODVjIFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWQ1YTUgXHVhYzA0XHVjMTIwXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gJCgxXFxsZSB2LHdcXGxlIE4pJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNzg4XHViYzE0XHVjNzc0XHVhYzAwIFx1Y2Q1Y1x1YzE4YyBcdWJhODcgXHVhYzFjXHVjNzU4IFx1YzBjOVx1YWU1NFx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzNDEzMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IltBXSBBcnRpc3RpYyBHcmFwaCBDb2xvcmluZyBUYXNrIiwiZGVzY3JpcHRpb24iOiI8cD5IZUJ5ZSBoYXMgZGVjaWRlZCB0byBjcmVhdGUgYSBuZXcgYXJ0d29yay4gQXMgc29tZW9uZSB3aG8gbGlrZXMgcHV0dGluZyBtZWFuaW5nIGluIGFsbCBoaXMgYXJ0d29yaywgSGVCeWUgaGFzIGRlY2lkZWQgdG8gdXNlJm5ic3A7dGhlIGZvbGxvd2luZyB0aG91Z2h0cyB0aGlzIHRpbWUuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VGhpcyBhcnR3b3JrIGlzIGJhc2VkIG9uIGRpcmVjdGVkIGFjeWNsaWMgZ3JhcGhzLCB3aGljaCBzeW1ib2xpemVzLCAmIzM5O0V2ZXJ5dGhpbmcgaGFzIGFuIG9yZGVyIGFuZCBmbG93IHRvIGl0LiYjMzk7PFwvbGk+XHJcblx0PGxpPlRoZW4sIHRvIHNob3cgdGhhdCBldmVyeXRoaW5nIGhhcyBpdHMgb3duIGNvbG9yLCBoZSB3aXNoZXMgdG8gY29sb3IgZWFjaCB2ZXJ0ZXggb2YgdGhlIGdyYXBoLjxcL2xpPlxyXG5cdDxsaT5JbiBhZGRpdGlvbiwgdG8gZXhwcmVzcyB0aGUgcG9pbnQmbmJzcDsmIzM5O1RoZXJlIGFyZSBuZXcgdGhpbmdzIGluIHRoZSB3b3JsZCBob3dtdWNoIGV2ZXIgeW91IGxvb2sgYXQgaXQmIzM5OywgaGUgcGxhbnMgdG8gbWFrZSBzdXJlIHRoZXJlIGlzIG5vIHBhdGggaW4gdGhlIGdyYXBoIHdoaWNoIGhhcyB0d28gdmVydGljZXMgd2l0aCB0aGUgc2FtZSBjb2xvci48XC9saT5cclxuXHQ8bGk+RmluYWxseSwgdG8gYm9keSB0aGUgdGhvdWdodCwgJiMzOTtEZXNwaXRlIGV2ZXJ5dGhpbmcsIHRoZXJlIGFyZSBtYW55IHNpbWlsYXJpdGllcyB3aGVuIHZpZXdlZCBmcm9tIGEgYnJvYWQgYW5nbGUmIzM5OywgdGhlIG51bWJlciBvZiBjb2xvcnMgdXNlZCBuZWVkcyB0byBiZSBtaW5pbWl6ZWQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+R2l2ZW4gdGhlIGRpcmVjdGVkIGFjeWxpYyBncmFwaCBIZUJ5ZSBpcyBnb2luZyB0byBiYXNlIGhpcyBhcnR3b3JrIG9uLCBmaW5kIHRoZSBtaW5pbXVtIG51bWJlciBjb2xvcnMgcmVxdWlyZWQgdG8gZW1ib2R5IGFsbCBvZiB0aGUgYWJvdmUgdGhvdWdodHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzICROJCBhbmQgJE0kLCBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGFuZCBlZGdlcyBpbiB0aGUgZ3JhcGgsIHJlc3BlY3RpdmVseS4gJCgxXFxsZSBOXFxsZSAyMDBcXCwgMDAwOyQgJDBcXGxlIE1cXGxlIDMwMFxcLCAwMDApJDxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgJE0kIGxpbmVzIG9mIGlucHV0IGNvbnRhaW5zIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgJHYkLCBhbmQgJHckLiBUaGlzIGRlbm90ZXMgdGhhdCB0aGVyZSBpcyBhIGRpcmVjdGVkIGVkZ2Ugc3RhcnRpbmcgYXQgdmVydGV4ICR2JCwgYW5kIGVuZGluZyBhdCB2ZXJ0ZXggJHckLiZuYnNwOyQoMVxcbGUgdix3XFxsZSBOKSQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCB0aGUgbWluaW11bSBudW1iZXIgb2YgY29sb3JzIG5lZWRlZCBmb3IgSGVCeWUgdG8gY29sb3IgdGhlIGdyYXBoIGluIHRoZSBmaXJzdCBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=