시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 64 MB 99 43 42 50.000%

문제

어느 나라에는, N개의 도시가 있다. 각각 1부터 N까지 번호가 매겨저 있다. 한 엔지니어는 모든 도시를 연결하는 길을 깔아야 한다. 즉, 어떤 도시에서라도 모든 도시를 갈 수 있고, 여러 도시를 통과할 수도 있어야 한다. 엔지니어가 속한 팀은 몇몇 노선을 정하기 위해 설문조사를 하였다.(두 도시 사이의 후보 도로). 노선은 서로 두 도시 사이에 양방향으로 연결되어있다. 그는 설문조사 한 노선에 특정 요금을 매기고 양방향 길을 지을 수 있다.(길이 짧을수록 비용은 더 싸다.)

이 엔지니어는 미리 도로 시스템을 구축한 적이 한번도 없다. 그는 그냥 그가 원하는 길을 하나 골라, 모든 도시가 연결될 때까지 짓는다.

기사는 p 도시에서 q 도시까지 연결되는 길을 지으려고 한다.

비용을 줄이기 위해서 들어온 정부의 압력으로, 길을 지어야 하는지 짓지 말아야 하는지를 나타내는 프로그램을 작성하려 한다.

입력

첫번째 줄에는 테스트 케이스 T ≤ 10 이 들어온다.

테스트 케이스는 모두 정수 N, M, p 와 q가 들어와야 한다. N(2 ≤ N ≤ 10 000)은 설문조사된 길이다. p와 q에 표시해야 하는 노선은(1 ≤ p ≤ N) (1 ≤ q ≤ N) 두 도시 사이에, 즉 엔지니어가 그가 길을 지을 수 있는지를 표시한다.

그런 다음, 다음 M 라인은 각각의 3개의 숫자인 U, V, W (1 U는 1 000 400 ≤ w ≤ N, 1 ≤ V의 ≤의 N을, ≤ ≤) U 사이의 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
W3sicHJvYmxlbV9pZCI6IjkzNDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFlMzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzViNFx1YjI5MCBcdWIwOThcdWI3N2NcdWM1ZDBcdWIyOTQsIE5cdWFjMWNcdWM3NTggXHViM2M0XHVjMmRjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhYzAxXHVhYzAxIDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODAwIFx1Yzc4OFx1YjJlNC4gXHVkNTVjIFx1YzVkNFx1YzljMFx1YjJjOFx1YzViNFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViM2M0XHVjMmRjXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWFlMzhcdWM3NDQgXHVhZTU0XHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWM1YjRcdWI1YTQgXHViM2M0XHVjMmRjXHVjNWQwXHVjMTFjXHViNzdjXHViM2M0IFx1YmFhOFx1YjRlMCBcdWIzYzRcdWMyZGNcdWI5N2MgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1YzVlY1x1YjdlYyBcdWIzYzRcdWMyZGNcdWI5N2MgXHVkMWI1XHVhY2ZjXHVkNTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM1ZDRcdWM5YzBcdWIyYzhcdWM1YjRcdWFjMDAgXHVjMThkXHVkNTVjIFx1ZDMwMFx1Yzc0MCBcdWJhODdcdWJhODcgXHViMTc4XHVjMTIwXHVjNzQ0IFx1YzgxNVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjMTI0XHViYjM4XHVjODcwXHVjMGFjXHViOTdjIFx1ZDU1OFx1YzYwMFx1YjJlNC4oXHViNDUwIFx1YjNjNFx1YzJkYyBcdWMwYWNcdWM3NzRcdWM3NTggXHVkNmM0XHViY2Y0IFx1YjNjNFx1Yjg1YykuIFx1YjE3OFx1YzEyMFx1Yzc0MCBcdWMxMWNcdWI4NWMgXHViNDUwIFx1YjNjNFx1YzJkYyBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVjNTkxXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViMjk0IFx1YzEyNFx1YmIzOFx1Yzg3MFx1YzBhYyBcdWQ1NWMgXHViMTc4XHVjMTIwXHVjNWQwIFx1ZDJiOVx1YzgxNSBcdWM2OTRcdWFlMDhcdWM3NDQgXHViOWU0XHVhZTMwXHVhY2UwIFx1YzU5MVx1YmMyOVx1ZDVhNSBcdWFlMzhcdWM3NDQgXHVjOWMwXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuKFx1YWUzOFx1Yzc3NCBcdWM5ZTdcdWM3NDRcdWMyMThcdWI4NWQgXHViZTQ0XHVjNmE5XHVjNzQwIFx1YjM1NCBcdWMyZjhcdWIyZTQuKTxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVjNWQ0XHVjOWMwXHViMmM4XHVjNWI0XHViMjk0IFx1YmJmOFx1YjlhYyBcdWIzYzRcdWI4NWMgXHVjMmRjXHVjMmE0XHVkMTVjXHVjNzQ0IFx1YWQ2Y1x1Y2Q5NVx1ZDU1YyBcdWM4MDFcdWM3NzQgXHVkNTVjXHViYzg4XHViM2M0IFx1YzVjNlx1YjJlNC4gXHVhZGY4XHViMjk0IFx1YWRmOFx1YjBlNSBcdWFkZjhcdWFjMDAgXHVjNmQwXHVkNTU4XHViMjk0IFx1YWUzOFx1Yzc0NCBcdWQ1NThcdWIwOTggXHVhY2U4XHViNzdjLCBcdWJhYThcdWI0ZTAgXHViM2M0XHVjMmRjXHVhYzAwIFx1YzVmMFx1YWNiMFx1YjQyMCBcdWI1NGNcdWFlNGNcdWM5YzAgXHVjOWQzXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFlMzBcdWMwYWNcdWIyOTQgcCBcdWIzYzRcdWMyZGNcdWM1ZDBcdWMxMWMgcSBcdWIzYzRcdWMyZGNcdWFlNGNcdWM5YzAgXHVjNWYwXHVhY2IwXHViNDE4XHViMjk0IFx1YWUzOFx1Yzc0NCBcdWM5YzBcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJlNDRcdWM2YTlcdWM3NDQgXHVjOTA0XHVjNzc0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWI0ZTRcdWM1YjRcdWM2MjggXHVjODE1XHViZDgwXHVjNzU4IFx1YzU1NVx1YjgyNVx1YzczY1x1Yjg1YywgXHVhZTM4XHVjNzQ0IFx1YzljMFx1YzViNFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzAgXHVjOWQzXHVjOWMwIFx1YjlkMFx1YzU0NFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0Jm5ic3A7VCAmbGU7IDEwIFx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViYWE4XHViNDUwIFx1YzgxNVx1YzIxOCBOLCBNLCBwIFx1YzY0MCBxXHVhYzAwIFx1YjRlNFx1YzViNFx1YzY0MFx1YzU3YyBcdWQ1NWNcdWIyZTQuIE4oMiAmbGU7IE4gJmxlOyAxMCAwMDApXHVjNzQwIFx1YzEyNFx1YmIzOFx1Yzg3MFx1YzBhY1x1YjQxYyBcdWFlMzhcdWM3NzRcdWIyZTQuIHBcdWM2NDAgcVx1YzVkMCBcdWQ0NWNcdWMyZGNcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YjE3OFx1YzEyMFx1Yzc0MCgxICZsZTsgcCAmbGU7IE4pICgxICZsZTsgcSAmbGU7IE4pIFx1YjQ1MCBcdWIzYzRcdWMyZGMgXHVjMGFjXHVjNzc0XHVjNWQwLCBcdWM5ODkgXHVjNWQ0XHVjOWMwXHViMmM4XHVjNWI0XHVhYzAwIFx1YWRmOFx1YWMwMCBcdWFlMzhcdWM3NDQgXHVjOWMwXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzBcdWI5N2MgXHVkNDVjXHVjMmRjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI3ZjAgXHViMmU0XHVjNzRjLCBcdWIyZTRcdWM3NGMgTSBcdWI3N2NcdWM3NzhcdWM3NDAgXHVhYzAxXHVhYzAxXHVjNzU4IDNcdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHVjNzc4Jm5ic3A7VSwgViwgVyAoMSBVXHViMjk0IDEgMDAwIDQwMCAmbGU7IHcgJmxlOyBOLCAxICZsZTsgVlx1Yzc1OCAmbGU7XHVjNzU4IE5cdWM3NDQsICZsZTsgJmxlOykgVSBcdWMwYWNcdWM3NzRcdWM3NTggdyBcdWFlMzhcdWM3NzRcdWM3NTggXHVjNTkxXHViYzI5XHVkNWE1IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWM3NGNcdWM3NDQgXHViMDk4XHVkMGMwXHViMGM1XHViMmM4XHViMmU0IFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM4MDggXHVkNjA0XHVjN2FjIFx1YzJkY1x1YzJhNFx1ZDE1Y1x1YzVkMFx1Yzc4OFx1YjI5NCBcdWFjMDEgXHViM2M0XHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWFjZTBcdWM3MjBcdWQ1NjlcdWIyYzhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCwgXHViNDUwIFx1YjNjNFx1YzJkYyBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNzU4IFx1YWMwMFx1YjJhNVx1ZDU1Y1x1YjNjNFx1YWMwMFx1Yzc4OFx1YjJlNC5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWIzYzRcdWI4NWMgXHVjMmRjXHVjMmE0XHVkMTVjXHVjNzc0IFx1YjQ1MCBcdWIzYzRcdWMyZGMgXHVhYzA0XHVjNzU4IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWIyOTRcdWM5YzAgXHViY2Y0XHVjN2E1XHVkNTVjXHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjMjJiXHVjNzkwXHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwXHVjMTFjIFx1YjljY1x1YzU3ZCBcdWM1ZDRcdWM5YzBcdWIyYzhcdWM1YjRcdWFjMDAgcC1xIFx1YWUzOFx1Yzc0NCBcdWFjMDBcdWM3YTUgXHVjOWU3XHVhYzhjIFx1YzljMFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0XHViYTc0IFlFU1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCBOT1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTM0NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJvYWQiLCJkZXNjcmlwdGlvbiI6IjxwPkluIG9uZSBjb3VudHJ5LCB0aGVyZSBhcmUgTiBjaXRpZXMsIG51bWJlcmVkIDEgdG8gTi4gQSBjaXZpbCBlbmdpbmVlciBoYXMgdG8gYnVpbGQgcHVibGljIHJvYWRzIHRoYXQgY29ubmVjdCBhbGwgdGhlIGNpdGllcyB0b2dldGhlciwgaS5lLiwgaXQgbXVzdCBiZSBwb3NzaWJsZSB0byB0cmF2ZWwgZnJvbSBhbGwgY2l0aWVzIHRvIGFueSBvdGhlciBjaXRpZXMsIG1heWJlIGdvaW5nIHRocm91Z2ggbXVsdGlwbGUgY2l0aWVzLiBIaXMgdGVhbSBoYXMgc3VydmV5ZWQgc2V2ZXJhbCByb3V0ZXMgKGNhbmRpZGF0ZSByb2FkIGJldHdlZW4gYW55IHR3byBjaXRpZXMpLiBFYWNoIHJvdXRlIGlzIGEgYmlkaXJlY3Rpb25hbCBjb25uZWN0aW9uIGJldHdlZW4gdHdvIGNpdGllcy4gSGUgY2FuIGJ1aWxkIGEgYmktZGlyZWN0aW9uYWwgcm9hZCBvbiB0aGUgc3VydmV5ZWQgcm91dGUgZm9yIGEgc3BlY2lmaWMgY29zdCAoVGhlIHNob3J0ZXIgdGhlIHJvdXRlIGlzIHRoZSBjaGVhcGVyIHRoZSByb2FkKS48XC9wPlxyXG5cclxuPHA+VGhpcyBlbmdpbmVlciBoYXMgbmV2ZXIgcGxhbm5lZCBhIHJvYWQgc3lzdGVtIGluIGFkdmFuY2UuIEhlIHdvdWxkIGp1c3QgcGljayBvbmUgb2YgdGhlIHJvdXRlcyBiYXNlZCBvbiBoaXMgcHJlZmVyZW5jZSwgYW5kIGJ1aWxkIGEgcm9hZCB1bnRpbCBhbGwgdGhlIGNpdGllcyBhcmUgY29ubmVjdGVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5SaWdodCBub3cgdGhpcyBlbmdpbmVlciBpcyBnb2luZyB0byBidWlsZCBhIHJvYWQgZnJvbSB0aGUgY2l0eSBwIHRvIHRoZSBjaXR5IHEuIFdpdGggcHJlc3N1cmUgZnJvbSB0aGUgZ292ZXJubWVudCB0byByZWR1Y2UgdGhlIGNvc3QsIGhlIGFza3MgeW91IHRvIHdyaXRlIGEgcHJvZ3JhbSB0byBkZWNpZGUsIGlmIGhlIHNob3VsZCBidWlsZCB0aGlzIHJvYWQgb3Igbm90LiBZb3VyIHByb2dyYW0gc2hvdWxkIHNheSB5ZXMgaWYgdGhlIGJ1aWxkaW5nIG9mIHRoaXMgcm9hZCBndWFyYW50ZWVkIHRoYXQgaXQgY2FuIGJlIHBhcnQgb2YgdGhlIHNob3J0ZXN0IHJvYWQgc3lzdGVtIHRoYXQgY29ubmVjdHMgYWxsIGNpdGllcyB0b2dldGhlci4gT3RoZXJ3aXNlLCB5b3VyIHByb2dyYW0gc2hvdWxkIHNheSBuby4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgaW5wdXQgaXMgYSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUICZsZTsgMTAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggdGVzdCBjYXNlIHN0YXJ0IHdpdGggYSBsaW5lIGNvbnRhaW5zIDQgaW50ZWdlcnMgTiwgTSwgcCwgYW5kIHEuIE4gKDIgJmxlOyBOICZsZTsgMTAgMDAwKSBpcyB0aGUgbnVtYmVyIG9mIGNpdGllcyBpbiB0aGlzIHJvYWQgc3lzdGVtLiBNICgxICZsZTsgTSAmbGU7IDIwIDAwMCkgaXMgdGhlIG51bWJlciBvZiBzdXJ2ZXllZCByb3V0ZXMuIHAgYW5kIHEgKDEgJmxlOyBwICZsZTsgTiBhbmQgMSAmbGU7IHEgJmxlOyBOKSBpbmRpY2F0ZSB0aGUgcm91dGUgYmV0d2VlbiB0d28gY2l0aWVzLCB0aGF0IHRoZSBlbmdpbmVlciBhc2tzIGlmIGhlIGNhbiBidWlsZCBhIHJvYWQgb3Igbm90LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGVuLCB0aGUgZWFjaCBvZiB0aGUgZm9sbG93aW5nIE0gbGluZXMgY29udGFpbnMgMyBudW1iZXJzIHUsIHYsIGFuZCB3ICgxICZsZTsgdSAmbGU7IE4sIDEgJmxlOyB2ICZsZTsgTiwgMSAmbGU7IHcgJmxlOyA0MDAgMDAwKSBpbmRpY2F0ZXMgdGhhdCB0aGVyZSBhcmUgdGhlIGJpZGlyZWN0aW9uYWwgcm91dGUgb2YgbGVuZ3RoIHcgYmV0d2VlbiB1IGFuZCB2LiBUaGUgbGVuZ3RoIG9mIGVhY2ggcm9hZCBpbiB0aGUgY3VycmVudCBzeXN0ZW0gaXMgdW5pcXVlLiBBbmQsIHRoZXJlIGlzIG9ubHkgb25lIHBvc3NpYmxlIHJvYWQgYmV0d2VlbiB0d28gY2l0aWVzLiBUaGUgaW5wdXQgZ3VhcmFudGVlcyB0aGF0IGF0IGxlYXN0IG9uZSByb2FkIHN5c3RlbSBoYXMgYSByb3V0ZSBiZXR3ZWVuIGFueSB0d28gY2l0aWVzLiBBbGwgbnVtYmVycyBhcmUgaW50ZWdlcjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgZGlzcGxheSBZRVMgaWYgdGhlIGVuZ2luZWVyIGNhbiBidWlsZCBhIHJvYWQgcC1xIGFzIHBhcnQgb2YgdGhlIHNob3J0ZXN0IHJvYWQgc3lzdGVtLiBPdGhlcndpc2UsIHByaW50IE5PLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==