문제
선인장 그래프란 모든 간선이 최대 하나의 단순 사이클에만 포함된 무향 그래프를 의미합니다. 흐즈로는 선인장 그래프를 하나 가지고 있으며, 각 간선에는 길이가 있습니다. 두 정점 $u,ドル $v$를 연결하며 길이가 $l$인 간선을 순서쌍 $(u,v,l)$로 표기합니다. 문득 흐즈로는 자신의 그래프를 보다가 이러한 생각을 하게 되었습니다.
- 어떤 선인장 그래프는 적당히 접어서 1차원으로 만들 수도 있지 않을까?
이 의문을 해결하기 전, 다음의 성질을 만족하는 그래프를 접어서 1차원으로 만들 수 있다고 정의합시다.
- 각 정점 $i$에 1차원 좌표 $x_i$를 배정하여, 각 간선 $(u,v,l)$에 대해 $|x_u-x_v|=l$이 성립하도록 할 수 있습니다.
이제 여러분이 해결해야 하는 문제는 다음과 같습니다. 입력으로 흐즈로가 가진 선인장 그래프가 주어집니다. 이 그래프를 접어서 1차원으로 만들 수 있는지 판단해 주세요.
출력
그래프를 접어서 1차원으로 만들 수 있다면, 한 줄에 YES를 출력하세요. 그렇지 않다면 NO를 출력하세요.
노트
본 문제에서 정의하는 선인장 그래프는 연결 그래프가 아닐 수 있음에 주의하세요.
W3sicHJvYmxlbV9pZCI6IjMxMjIzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMTIwXHVjNzc4XHVjN2E1IFx1YzgxMVx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+PHN0cm9uZz5cdWMxMjBcdWM3NzhcdWM3YTUgXHVhZGY4XHViNzk4XHVkNTA0PFwvc3Ryb25nPlx1Yjc4MCBcdWJhYThcdWI0ZTAgXHVhYzA0XHVjMTIwXHVjNzc0IFx1Y2Q1Y1x1YjMwMCBcdWQ1NThcdWIwOThcdWM3NTggXHViMmU4XHVjMjFjIFx1YzBhY1x1Yzc3NFx1ZDA3NFx1YzVkMFx1YjljYyBcdWQzZWNcdWQ1NjhcdWI0MWMgXHViYjM0XHVkNWE1IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NjlcdWIyYzhcdWIyZTQuIFx1ZDc1MFx1Yzk4OFx1Yjg1Y1x1YjI5NCBcdWMxMjBcdWM3NzhcdWM3YTUgXHVhZGY4XHViNzk4XHVkNTA0XHViOTdjIFx1ZDU1OFx1YjA5OCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWFjMDEgXHVhYzA0XHVjMTIwXHVjNWQwXHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YjQ1MCBcdWM4MTVcdWM4MTAgJHUkLCAkdiRcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViYTcwIFx1YWUzOFx1Yzc3NFx1YWMwMCAkbCRcdWM3NzggXHVhYzA0XHVjMTIwXHVjNzQ0IFx1YzIxY1x1YzExY1x1YzMwZCAkKHUsdixsKSRcdWI4NWMgXHVkNDVjXHVhZTMwXHVkNTY5XHViMmM4XHViMmU0LiBcdWJiMzhcdWI0ZGQgXHVkNzUwXHVjOTg4XHViODVjXHViMjk0IFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWFkZjhcdWI3OThcdWQ1MDRcdWI5N2MgXHViY2Y0XHViMmU0XHVhYzAwIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWMwZGRcdWFjMDFcdWM3NDQgXHVkNTU4XHVhYzhjIFx1YjQxOFx1YzVjOFx1YzJiNVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM1YjRcdWI1YTQgXHVjMTIwXHVjNzc4XHVjN2E1IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YjI5NCBcdWM4MDFcdWIyZjlcdWQ3ODggXHVjODExXHVjNWI0XHVjMTFjIDFcdWNjMjhcdWM2ZDBcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQ0XHVhZTRjPzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1Yzc3NCBcdWM3NThcdWJiMzhcdWM3NDQgXHVkNTc0XHVhY2IwXHVkNTU4XHVhZTMwIFx1YzgwNCwgXHViMmU0XHVjNzRjXHVjNzU4IFx1YzEzMVx1YzljOFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhZGY4XHViNzk4XHVkNTA0XHViOTdjIDxzdHJvbmc+XHVjODExXHVjNWI0XHVjMTFjIDFcdWNjMjhcdWM2ZDBcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQ8XC9zdHJvbmc+XHVhY2UwIFx1YzgxNVx1Yzc1OFx1ZDU2OVx1YzJkY1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWFjMDEgXHVjODE1XHVjODEwICRpJFx1YzVkMCAxXHVjYzI4XHVjNmQwIFx1Yzg4Y1x1ZDQ1YyAkeF9pJFx1Yjk3YyBcdWJjMzBcdWM4MTVcdWQ1NThcdWM1ZWMsIFx1YWMwMSBcdWFjMDRcdWMxMjAgJCh1LHYsbCkkXHVjNWQwIFx1YjMwMFx1ZDU3NCAkfHhfdS14X3Z8PWwkXHVjNzc0IFx1YzEzMVx1YjliZFx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzJiNVx1YjJjOFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM3NzRcdWM4MWMgXHVjNWVjXHViN2VjXHViZDg0XHVjNzc0IFx1ZDU3NFx1YWNiMFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHViYjM4XHVjODFjXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWMyYjVcdWIyYzhcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWQ3NTBcdWM5ODhcdWI4NWNcdWFjMDAgXHVhYzAwXHVjOWM0IDxzdHJvbmc+XHVjMTIwXHVjNzc4XHVjN2E1IFx1YWRmOFx1Yjc5OFx1ZDUwNDxcL3N0cm9uZz5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiBcdWM3NzQgXHVhZGY4XHViNzk4XHVkNTA0XHViOTdjIDxzdHJvbmc+XHVjODExXHVjNWI0XHVjMTFjIDFcdWNjMjhcdWM2ZDBcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODg8XC9zdHJvbmc+XHViMjk0XHVjOWMwIFx1ZDMxMFx1YjJlOFx1ZDU3NCBcdWM4ZmNcdWMxMzhcdWM2OTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHVjODE1XHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCAkbiRcdWFjZmMgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YWMxY1x1YzIxOCAkbSRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YmQ4NFx1YjlhY1x1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuICgkMSBcXGxlIG4gXFxsZSAxMF41LCAwIFxcbGUgbSBcXGxlIFxcbWluKFxcbGZsb29yIDEuNShuLTEpIFxccmZsb29yLDEwXjUpJCk8XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgXHVjZDFkICRtJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuIFx1YWRmOCBcdWM5MTEgJGkkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAkaSRcdWJjODhcdWM5ZjggXHVhYzA0XHVjMTIwXHVjNzc0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjODEwICR1X2kkXHVjNjQwICR2X2kkLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YWUzOFx1Yzc3NCAkbF9pJFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHViZDg0XHViOWFjXHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gKCQxIFxcbGUgdV9pLHZfaSBcXGxlIG4kLCAkdSBcXG5lcSB2JCwgJDAgXFxsZSBsX2kgXFxsZSA1MCQpPFwvcD5cclxuXHJcbjxwPlx1YzhmY1x1YzViNFx1YzljNCBcdWFkZjhcdWI3OThcdWQ1MDRcdWIyOTQgXHVjOTExXHViY2Y1IFx1YWMwNFx1YzEyMFx1Yzc3NFx1YjA5OCBcdWM3OTBcdWFlMzAgXHVjNzkwXHVjMmUwXHVjNzQ0IFx1ZDVhNVx1ZDU1OFx1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3MCwgXHVjMTIwXHVjNzc4XHVjN2E1IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc4NFx1Yzc3NCBcdWJjZjRcdWM3YTVcdWI0MjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhZGY4XHViNzk4XHVkNTA0XHViOTdjIDxzdHJvbmc+XHVjODExXHVjNWI0XHVjMTFjIDFcdWNjMjhcdWM2ZDBcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODg8XC9zdHJvbmc+XHViMmU0XHViYTc0LCBcdWQ1NWMgXHVjOTA0XHVjNWQwIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT48c3Ryb25nPllFUzxcL3N0cm9uZz48XC9jb2RlPjxcL3NwYW4+XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzEzOFx1YzY5NC4gXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YjJlNFx1YmE3NCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+PHN0cm9uZz5OTzxcL3N0cm9uZz48XC9jb2RlPjxcL3NwYW4+XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzEzOFx1YzY5NC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHViY2Y4IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWM4MTVcdWM3NThcdWQ1NThcdWIyOTQgPHN0cm9uZz5cdWMxMjBcdWM3NzhcdWM3YTUgXHVhZGY4XHViNzk4XHVkNTA0PFwvc3Ryb25nPlx1YjI5NCBcdWM1ZjBcdWFjYjAgXHVhZGY4XHViNzk4XHVkNTA0XHVhYzAwIFx1YzU0NFx1YjJkMCBcdWMyMTggXHVjNzg4XHVjNzRjXHVjNWQwIFx1YzhmY1x1Yzc1OFx1ZDU1OFx1YzEzOFx1YzY5NC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMxMjIzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2FjdHVzIEZvbGRpbmciLCJkZXNjcmlwdGlvbiI6IjxwPkEgPHN0cm9uZz5jYWN0dXMgZ3JhcGg8XC9zdHJvbmc+IGlzIGFuIHVuZGlyZWN0ZWQgZ3JhcGggd2hlcmUgZWFjaCBlZGdlIGlzIGluY2x1ZGVkIGluIGF0IG1vc3Qgb25lIHNpbXBsZSBjeWNsZS4gQ2hyb21hdGUgaGFzIGEgY2FjdHVzIGdyYXBoLCB3aGVyZSBlYWNoIGVkZ2UgaGFzIGEgY2VydGFpbiBsZW5ndGguIFRoZSBlZGdlIGNvbm5lY3RpbmcgJHUkIGFuZCAkdiQgd2l0aCBsZW5ndGggJGwkLCBpcyBkZW5vdGVkIGFzIGEgdHVwbGUgJCh1LHYsbCkkLiBMb29raW5nIGF0IGhpcyBncmFwaCwgQ2hyb21hdGUgY2FtZSB1cCB3aXRoIHRoaXMgaWRlYS48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5Xb3VsZCBpdCBiZSBwb3NzaWJsZSB0byBmb2xkIHNvbWUgY2FjdHVzIGdyYXBocyBpbnRvIG9uZSBkaW1lbnNpb24/PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+QmVmb3JlIGRlYWxpbmcgd2l0aCB0aGlzIHF1ZXN0aW9uLCBsZXQgdXMgY2FsbCBhIGdyYXBoIDxzdHJvbmc+Zm9sZGFibGUgaW50byBvbmUgZGltZW5zaW9uPFwvc3Ryb25nPiBpZiBpdCBzYXRpc2ZpZXMgdGhlIGZvbGxvd2luZyBjb25kaXRpb24uPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+SXQgaXMgcG9zc2libGUgdG8gbWFrZSAkfHhfdS14X3Z8PWwkIGhvbGQgZm9yIGV2ZXJ5IGVkZ2UgJCh1LHYsbCkkLCBieSBhc3NpZ25pbmcgYW4gb25lLWRpbWVuc2lvbmFsIGNvb3JkaW5hdGUgJHhfaSQgdG8gZWFjaCB2ZXJ0ZXggJGkkLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPk5vdyB0aGUgdGFzayBpcyBhcyBmb2xsb3dzLiBDaHJvbWF0ZSYjMzk7cyA8c3Ryb25nPmNhY3R1cyBncmFwaDxcL3N0cm9uZz4gaXMgZ2l2ZW4gYXMgaW5wdXQuIFBsZWFzZSBkZXRlcm1pbmUgaWYgdGhlIGdyYXBoIGlzIDxzdHJvbmc+Zm9sZGFibGUgaW50byBvbmUgZGltZW5zaW9uPFwvc3Ryb25nPi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lLCB0d28gaW50ZWdlcnMgJG4kIGFuZCAkbSQgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGFuZCBlZGdlcyAmbWRhc2g7IGFyZSBnaXZlbi4gKCQxIFxcbGUgbiBcXGxlIDEwXjUsIDAgXFxsZSBtIFxcbGUgXFxtaW4oXFxsZmxvb3IgMS41KG4tMSkgXFxyZmxvb3IsMTBeNSkkKTxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nICRtJCBsaW5lcyBjb250YWluIGluZm9ybWF0aW9uIG9mIHRoZSBlZGdlcy4gVGhlICRpJC10aCBsaW5lIG91dCBvZiB0aGVtIGNvbnRhaW5zIHRoZSB0d28gdmVydGljZXMgJHVfaSQgYW5kICR2X2kkIGNvbm5lY3RlZCBieSB0aGUgJGkkLXRoIGVkZ2UsIGFuZCAkbF9pJCwgdGhlIGxlbmd0aCBvZiB0aGUgZWRnZS4gKCQxIFxcbGUgdV9pLHZfaSBcXGxlIG4kLCAkdSBcXG5lcSB2JCwgJDAgXFxsZSBsX2kgXFxsZSA1MCQpPFwvcD5cclxuXHJcbjxwPlRoZSBncmFwaCBkb2VzIG5vdCBoYXZlIGR1cGxpY2F0ZSBlZGdlcyBvciBzZWxmIGxvb3BzLCBhbmQgaXMgZ3VhcmFudGVlZCB0byBiZSBhIGNhY3R1cyBncmFwaC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JZiB0aGUgZ3JhcGggaXMgPHN0cm9uZz5mb2xkYWJsZSBpbnRvIG9uZSBkaW1lbnNpb248XC9zdHJvbmc+LCBvdXRwdXQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjx0dD48c3Ryb25nPllFUzxcL3N0cm9uZz48XC90dD48XC9zcGFuPiBvbiBvbmUgbGluZS4gT3RoZXJ3aXNlLCBvdXRwdXQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjx0dD48c3Ryb25nPk5PPFwvc3Ryb25nPjxcL3R0PjxcL3NwYW4+LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5EbyBub3RlIHRoYXQgdGhlIDxzdHJvbmc+Y2FjdHVzIGdyYXBoPFwvc3Ryb25nPiBkZWZpbmVkIGluIHRoaXMgdGFzayBpcyBub3QgbmVjZXNzYXJpbHkmbmJzcDthIGNvbm5lY3RlZCBncmFwaC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=