시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 64 MB 105 51 47 54.023%

문제

어떤 나라에는 1부터 N까지 이름 붙여진 N개의 도시가 있다. 한 엔지니어는 모든 도시를 연결하는 도로를 건설하고자 한다. 즉, 모든 도시에 대해 항상 다른 어떤 도시로든 이동할 수 있어야 한다. 이때 여러 개의 도시를 통과할 수도 있다. 그의 팀은 몇 개의 길(도로 후보)을 조사했다. 각각의 길은 두 도시를 양방향으로 잇는다. 길 위에 도로를 지을 때는 특정 비용이 든다. (길이 짧을수록 비용도 싸다.)

이 엔지니어는 교통 시스템을 미리 계획하지 않았다. 그는 그저 선호에 따라 한 개의 길을 선택하고, 도로를 건설하는 일을 모든 도시가 연결될 때까지 반복한다.

지금 엔지니어는 도시 p와 도시 q를 잇는 도로를 건설하고자 한다. 비용을 감축하라는 정부의 압력에 의해, 그는 당신에게 그가 해당 도로를 지어야 하는지 여부를 판단하는 프로그램을 작성할 것을 요구했다. 당신의 프로그램은 그 도로를 지으면서 모든 도시를 연결하는 가장 짧은 도로망을 만들 수 있으면 YES라고 대답해야 한다. 그렇지 않다면, NO를 출력해야 한다.

입력

첫 줄에 테스트 케이스의 개수 T가 주어진다. (T ≤ 10) 

각 테스트 케이스의 첫 줄에는 4개의 정수 N, M, p, q가 주어진다. N(2 ≤ N ≤ 10,000)은 도로망 위에 존재하는 도시의 수이다. M(1 ≤ M ≤ 20,000)은 길의 수이다. p와 q(1 ≤ p,q ≤ N)는 그 사이에 도로를 지어도 되는지 판단해야 하는 두 도시이다.

이어지는 M개의 줄 각각에는 u, v, w가 주어진다.(1 ≤ u ≤ N, 1 ≤ v ≤ N, 1 ≤ w ≤ 400,000) 도시 u와 v를 잇는 양방향 길의 비용이 w라는 것을 의미한다. 도로를 짓는 데 드는 비용은 모두 다르며, 두 도시를 잇는 길은 오직 하나이다. 모든 도시를 잇는 도로망이 최소 한 개 이상 존재한다는 것이 보장된다. 모든 입력은 정수이다.

출력

각 테스트 케이스에 대해, p-q를 지으면서 가장 짧은 도로망을 만들 수 있으면 YES를 출력한다. 아니면 NO를 출력한다.

예제 입력 1

3
2 1 1 2
1 2 4
3 3 2 3
1 2 1
1 3 2
2 3 3
4 5 3 4
1 2 1
1 3 3
3 4 2
1 4 4
4 2 5

예제 출력 1

YES
NO
YES
W3sicHJvYmxlbV9pZCI6IjkzNDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzYzRcdWI4NWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzViNFx1YjVhNCBcdWIwOThcdWI3N2NcdWM1ZDBcdWIyOTQgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1Yzc3NFx1Yjk4NCBcdWJkOTlcdWM1ZWNcdWM5YzQgTlx1YWMxY1x1Yzc1OCBcdWIzYzRcdWMyZGNcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWQ1NWMgXHVjNWQ0XHVjOWMwXHViMmM4XHVjNWI0XHViMjk0IFx1YmFhOFx1YjRlMCBcdWIzYzRcdWMyZGNcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWFjNzRcdWMxMjRcdWQ1NThcdWFjZTBcdWM3OTAgXHVkNTVjXHViMmU0LiBcdWM5ODksIFx1YmFhOFx1YjRlMCBcdWIzYzRcdWMyZGNcdWM1ZDAgXHViMzAwXHVkNTc0IFx1ZDU2ZFx1YzBjMSBcdWIyZTRcdWI5NzggXHVjNWI0XHViNWE0IFx1YjNjNFx1YzJkY1x1Yjg1Y1x1YjRlMCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWQxYjVcdWFjZmNcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4mbmJzcDtcdWFkZjhcdWM3NTggXHVkMzAwXHVjNzQwIFx1YmE4NyBcdWFjMWNcdWM3NTggXHVhZTM4KFx1YjNjNFx1Yjg1YyBcdWQ2YzRcdWJjZjQpXHVjNzQ0IFx1Yzg3MFx1YzBhY1x1ZDU4OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWUzOFx1Yzc0MCBcdWI0NTAgXHViM2M0XHVjMmRjXHViOTdjIFx1YzU5MVx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM3ODdcdWIyOTRcdWIyZTQuIFx1YWUzOCBcdWM3MDRcdWM1ZDAgXHViM2M0XHViODVjXHViOTdjIFx1YzljMFx1Yzc0NCBcdWI1NGNcdWIyOTQgXHVkMmI5XHVjODE1IFx1YmU0NFx1YzZhOVx1Yzc3NCBcdWI0ZTBcdWIyZTQuIChcdWFlMzhcdWM3NzQgXHVjOWU3XHVjNzQ0XHVjMjE4XHViODVkIFx1YmU0NFx1YzZhOVx1YjNjNCBcdWMyZjhcdWIyZTQuKTxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVjNWQ0XHVjOWMwXHViMmM4XHVjNWI0XHViMjk0IFx1YWQ1MFx1ZDFiNSBcdWMyZGNcdWMyYTRcdWQxNWNcdWM3NDQgXHViYmY4XHViOWFjIFx1YWNjNFx1ZDY4ZFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NThcdWIyZTQuIFx1YWRmOFx1YjI5NCBcdWFkZjhcdWM4MDAgXHVjMTIwXHVkNjM4XHVjNWQwIFx1YjUzMFx1Yjc3YyBcdWQ1NWMgXHVhYzFjXHVjNzU4IFx1YWUzOFx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NThcdWFjZTAsIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWFjNzRcdWMxMjRcdWQ1NThcdWIyOTQgXHVjNzdjXHVjNzQ0IFx1YmFhOFx1YjRlMCBcdWIzYzRcdWMyZGNcdWFjMDAgXHVjNWYwXHVhY2IwXHViNDIwIFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWJjMThcdWJjZjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YWUwOCBcdWM1ZDRcdWM5YzBcdWIyYzhcdWM1YjRcdWIyOTQgXHViM2M0XHVjMmRjIHBcdWM2NDAgXHViM2M0XHVjMmRjIHFcdWI5N2MgXHVjNzg3XHViMjk0IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWFjNzRcdWMxMjRcdWQ1NThcdWFjZTBcdWM3OTAgXHVkNTVjXHViMmU0LiBcdWJlNDRcdWM2YTlcdWM3NDQgXHVhYzEwXHVjZDk1XHVkNTU4XHViNzdjXHViMjk0IFx1YzgxNVx1YmQ4MFx1Yzc1OCBcdWM1NTVcdWI4MjVcdWM1ZDAgXHVjNzU4XHVkNTc0LCBcdWFkZjhcdWIyOTQgXHViMmY5XHVjMmUwXHVjNWQwXHVhYzhjIFx1YWRmOFx1YWMwMCBcdWQ1NzRcdWIyZjkgXHViM2M0XHViODVjXHViOTdjIFx1YzljMFx1YzViNFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzAgXHVjNWVjXHViZDgwXHViOTdjIFx1ZDMxMFx1YjJlOFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTYwIFx1YWM4M1x1Yzc0NCBcdWM2OTRcdWFkNmNcdWQ1ODhcdWIyZTQuIFx1YjJmOVx1YzJlMFx1Yzc1OCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDAgXHVhZGY4IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWM5YzBcdWM3M2NcdWJhNzRcdWMxMWMgXHViYWE4XHViNGUwIFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWIzYzRcdWI4NWNcdWI5ZGRcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzQgWUVTXHViNzdjXHVhY2UwIFx1YjMwMFx1YjJmNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YzljMCBcdWM1NGFcdWIyZTRcdWJhNzQsIE5PXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOyhUICZsZTsgMTApJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgNFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggTiwgTSwgcCwgcVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE4oMiAmbGU7IE4gJmxlOyAxMCwwMDApXHVjNzQwIFx1YjNjNFx1Yjg1Y1x1YjlkZCBcdWM3MDRcdWM1ZDAgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWMyMThcdWM3NzRcdWIyZTQuIE0oMSAmbGU7IE0gJmxlOyAyMCwwMDApXHVjNzQwIFx1YWUzOFx1Yzc1OCBcdWMyMThcdWM3NzRcdWIyZTQuIHBcdWM2NDAgcSgxICZsZTsgcCxxICZsZTsgTilcdWIyOTQgXHVhZGY4IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVjOWMwXHVjNWI0XHViM2M0IFx1YjQxOFx1YjI5NFx1YzljMCBcdWQzMTBcdWIyZThcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YjQ1MCBcdWIzYzRcdWMyZGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzViNFx1YzljMFx1YjI5NCBNXHVhYzFjXHVjNzU4IFx1YzkwNCBcdWFjMDFcdWFjMDFcdWM1ZDBcdWIyOTQgdSwgdiwgd1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuKDEgJmxlOyB1ICZsZTsgTiwgMSAmbGU7IHYgJmxlOyBOLCAxICZsZTsgdyAmbGU7IDQwMCwwMDApIFx1YjNjNFx1YzJkYyB1XHVjNjQwIHZcdWI5N2MgXHVjNzg3XHViMjk0IFx1YzU5MVx1YmMyOVx1ZDVhNSBcdWFlMzhcdWM3NTggXHViZTQ0XHVjNmE5XHVjNzc0IHdcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHViM2M0XHViODVjXHViOTdjIFx1YzlkM1x1YjI5NCBcdWIzNzAgXHViNGRjXHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc0MCBcdWJhYThcdWI0NTAgXHViMmU0XHViOTc0XHViYTcwLCBcdWI0NTAgXHViM2M0XHVjMmRjXHViOTdjIFx1Yzc4N1x1YjI5NCBcdWFlMzhcdWM3NDAgXHVjNjI0XHVjOWMxIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWM3ODdcdWIyOTQgXHViM2M0XHViODVjXHViOWRkXHVjNzc0IFx1Y2Q1Y1x1YzE4YyBcdWQ1NWMgXHVhYzFjIFx1Yzc3NFx1YzBjMSBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmNmNFx1YzdhNVx1YjQxY1x1YjJlNC4gXHViYWE4XHViNGUwIFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0LCBwLXFcdWI5N2MgXHVjOWMwXHVjNzNjXHViYTc0XHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHViM2M0XHViODVjXHViOWRkXHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTc0IFlFU1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzU0NFx1YjJjOFx1YmE3NCBOT1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTM0NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJvYWQiLCJkZXNjcmlwdGlvbiI6IjxwPkluIG9uZSBjb3VudHJ5LCB0aGVyZSBhcmUgTiBjaXRpZXMsIG51bWJlcmVkIDEgdG8gTi4gQSBjaXZpbCBlbmdpbmVlciBoYXMgdG8gYnVpbGQgcHVibGljIHJvYWRzIHRoYXQgY29ubmVjdCBhbGwgdGhlIGNpdGllcyB0b2dldGhlciwgaS5lLiwgaXQgbXVzdCBiZSBwb3NzaWJsZSB0byB0cmF2ZWwgZnJvbSBhbGwgY2l0aWVzIHRvIGFueSBvdGhlciBjaXRpZXMsIG1heWJlIGdvaW5nIHRocm91Z2ggbXVsdGlwbGUgY2l0aWVzLiBIaXMgdGVhbSBoYXMgc3VydmV5ZWQgc2V2ZXJhbCByb3V0ZXMgKGNhbmRpZGF0ZSByb2FkIGJldHdlZW4gYW55IHR3byBjaXRpZXMpLiBFYWNoIHJvdXRlIGlzIGEgYmlkaXJlY3Rpb25hbCBjb25uZWN0aW9uIGJldHdlZW4gdHdvIGNpdGllcy4gSGUgY2FuIGJ1aWxkIGEgYmktZGlyZWN0aW9uYWwgcm9hZCBvbiB0aGUgc3VydmV5ZWQgcm91dGUgZm9yIGEgc3BlY2lmaWMgY29zdCAoVGhlIHNob3J0ZXIgdGhlIHJvdXRlIGlzIHRoZSBjaGVhcGVyIHRoZSByb2FkKS48XC9wPlxyXG5cclxuPHA+VGhpcyBlbmdpbmVlciBoYXMgbmV2ZXIgcGxhbm5lZCBhIHJvYWQgc3lzdGVtIGluIGFkdmFuY2UuIEhlIHdvdWxkIGp1c3QgcGljayBvbmUgb2YgdGhlIHJvdXRlcyBiYXNlZCBvbiBoaXMgcHJlZmVyZW5jZSwgYW5kIGJ1aWxkIGEgcm9hZCB1bnRpbCBhbGwgdGhlIGNpdGllcyBhcmUgY29ubmVjdGVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5SaWdodCBub3cgdGhpcyBlbmdpbmVlciBpcyBnb2luZyB0byBidWlsZCBhIHJvYWQgZnJvbSB0aGUgY2l0eSBwIHRvIHRoZSBjaXR5IHEuIFdpdGggcHJlc3N1cmUgZnJvbSB0aGUgZ292ZXJubWVudCB0byByZWR1Y2UgdGhlIGNvc3QsIGhlIGFza3MgeW91IHRvIHdyaXRlIGEgcHJvZ3JhbSB0byBkZWNpZGUsIGlmIGhlIHNob3VsZCBidWlsZCB0aGlzIHJvYWQgb3Igbm90LiBZb3VyIHByb2dyYW0gc2hvdWxkIHNheSB5ZXMgaWYgdGhlIGJ1aWxkaW5nIG9mIHRoaXMgcm9hZCBndWFyYW50ZWVkIHRoYXQgaXQgY2FuIGJlIHBhcnQgb2YgdGhlIHNob3J0ZXN0IHJvYWQgc3lzdGVtIHRoYXQgY29ubmVjdHMgYWxsIGNpdGllcyB0b2dldGhlci4gT3RoZXJ3aXNlLCB5b3VyIHByb2dyYW0gc2hvdWxkIHNheSBuby4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgaW5wdXQgaXMgYSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUICZsZTsgMTAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggdGVzdCBjYXNlIHN0YXJ0IHdpdGggYSBsaW5lIGNvbnRhaW5zIDQgaW50ZWdlcnMgTiwgTSwgcCwgYW5kIHEuIE4gKDIgJmxlOyBOICZsZTsgMTAgMDAwKSBpcyB0aGUgbnVtYmVyIG9mIGNpdGllcyBpbiB0aGlzIHJvYWQgc3lzdGVtLiBNICgxICZsZTsgTSAmbGU7IDIwIDAwMCkgaXMgdGhlIG51bWJlciBvZiBzdXJ2ZXllZCByb3V0ZXMuIHAgYW5kIHEgKDEgJmxlOyBwICZsZTsgTiBhbmQgMSAmbGU7IHEgJmxlOyBOKSBpbmRpY2F0ZSB0aGUgcm91dGUgYmV0d2VlbiB0d28gY2l0aWVzLCB0aGF0IHRoZSBlbmdpbmVlciBhc2tzIGlmIGhlIGNhbiBidWlsZCBhIHJvYWQgb3Igbm90LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGVuLCB0aGUgZWFjaCBvZiB0aGUgZm9sbG93aW5nIE0gbGluZXMgY29udGFpbnMgMyBudW1iZXJzIHUsIHYsIGFuZCB3ICgxICZsZTsgdSAmbGU7IE4sIDEgJmxlOyB2ICZsZTsgTiwgMSAmbGU7IHcgJmxlOyA0MDAgMDAwKSBpbmRpY2F0ZXMgdGhhdCB0aGVyZSBhcmUgdGhlIGJpZGlyZWN0aW9uYWwgcm91dGUgb2YgbGVuZ3RoIHcgYmV0d2VlbiB1IGFuZCB2LiBUaGUgbGVuZ3RoIG9mIGVhY2ggcm9hZCBpbiB0aGUgY3VycmVudCBzeXN0ZW0gaXMgdW5pcXVlLiBBbmQsIHRoZXJlIGlzIG9ubHkgb25lIHBvc3NpYmxlIHJvYWQgYmV0d2VlbiB0d28gY2l0aWVzLiBUaGUgaW5wdXQgZ3VhcmFudGVlcyB0aGF0IGF0IGxlYXN0IG9uZSByb2FkIHN5c3RlbSBoYXMgYSByb3V0ZSBiZXR3ZWVuIGFueSB0d28gY2l0aWVzLiBBbGwgbnVtYmVycyBhcmUgaW50ZWdlcjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgZGlzcGxheSBZRVMgaWYgdGhlIGVuZ2luZWVyIGNhbiBidWlsZCBhIHJvYWQgcC1xIGFzIHBhcnQgb2YgdGhlIHNob3J0ZXN0IHJvYWQgc3lzdGVtLiBPdGhlcndpc2UsIHByaW50IE5PLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==