시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCZuYnNwO1QgJmxlOyAxMCBcdWM3NzQgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YmFhOFx1YjQ1MCBcdWM4MTVcdWMyMTggTiwgTSwgcCBcdWM2NDAgcVx1YWMwMCBcdWI0ZTRcdWM1YjRcdWM2NDBcdWM1N2MgXHVkNTVjXHViMmU0LiBOKDIgJmxlOyBOICZsZTsgMTAgMDAwKVx1Yzc0MCBcdWMxMjRcdWJiMzhcdWM4NzBcdWMwYWNcdWI0MWMgXHVhZTM4XHVjNzc0XHViMmU0LiBwXHVjNjQwIHFcdWM1ZDAgXHVkNDVjXHVjMmRjXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWIxNzhcdWMxMjBcdWM3NDAoMSAmbGU7IHAgJmxlOyBOKSAoMSAmbGU7IHEgJmxlOyBOKSBcdWI0NTAgXHViM2M0XHVjMmRjIFx1YzBhY1x1Yzc3NFx1YzVkMCwgXHVjOTg5IFx1YzVkNFx1YzljMFx1YjJjOFx1YzViNFx1YWMwMCBcdWFkZjhcdWFjMDAgXHVhZTM4XHVjNzQ0IFx1YzljMFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwXHViOTdjIFx1ZDQ1Y1x1YzJkY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViN2YwIFx1YjJlNFx1Yzc0YywgXHViMmU0XHVjNzRjIE0gXHViNzdjXHVjNzc4XHVjNzQwIFx1YWMwMVx1YWMwMVx1Yzc1OCAzXHVhYzFjXHVjNzU4IFx1YzIyYlx1Yzc5MFx1Yzc3OCZuYnNwO1UsIFYsIFcgKDEgVVx1YjI5NCAxIDAwMCA0MDAgJmxlOyB3ICZsZTsgTiwgMSAmbGU7IFZcdWM3NTggJmxlO1x1Yzc1OCBOXHVjNzQ0LCAmbGU7ICZsZTspIFUgXHVjMGFjXHVjNzc0XHVjNzU4IHcgXHVhZTM4XHVjNzc0XHVjNzU4IFx1YzU5MVx1YmMyOVx1ZDVhNSBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjNzg4XHVjNzRjXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBjNVx1YjJjOFx1YjJlNCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjODA4IFx1ZDYwNFx1YzdhYyBcdWMyZGNcdWMyYTRcdWQxNWNcdWM1ZDBcdWM3ODhcdWIyOTQgXHVhYzAxIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVhY2UwXHVjNzIwXHVkNTY5XHViMmM4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAsIFx1YjQ1MCBcdWIzYzRcdWMyZGMgXHVjMGFjXHVjNzc0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWFjMDBcdWIyYTVcdWQ1NWNcdWIzYzRcdWFjMDBcdWM3ODhcdWIyZTQuXHVjNzg1XHViODI1XHVjNzQwIFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NThcdWIwOThcdWM3NTggXHViM2M0XHViODVjIFx1YzJkY1x1YzJhNFx1ZDE1Y1x1Yzc3NCBcdWI0NTAgXHViM2M0XHVjMmRjIFx1YWMwNFx1Yzc1OCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjNzg4XHViMjk0XHVjOWMwIFx1YmNmNFx1YzdhNVx1ZDU1Y1x1YjJlNC4gXHViYWE4XHViNGUwIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMFx1YzExYyBcdWI5Y2NcdWM1N2QgXHVjNWQ0XHVjOWMwXHViMmM4XHVjNWI0XHVhYzAwIHAtcSBcdWFlMzhcdWM3NDQgXHVhYzAwXHVjN2E1IFx1YzllN1x1YWM4YyBcdWM5YzBcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YmE3NCBZRVNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTRcdWJhNzQgTk9cdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkzNDQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSb2FkIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBvbmUgY291bnRyeSwgdGhlcmUgYXJlIE4gY2l0aWVzLCBudW1iZXJlZCAxIHRvIE4uIEEgY2l2aWwgZW5naW5lZXIgaGFzIHRvIGJ1aWxkIHB1YmxpYyByb2FkcyB0aGF0IGNvbm5lY3QgYWxsIHRoZSBjaXRpZXMgdG9nZXRoZXIsIGkuZS4sIGl0IG11c3QgYmUgcG9zc2libGUgdG8gdHJhdmVsIGZyb20gYWxsIGNpdGllcyB0byBhbnkgb3RoZXIgY2l0aWVzLCBtYXliZSBnb2luZyB0aHJvdWdoIG11bHRpcGxlIGNpdGllcy4gSGlzIHRlYW0gaGFzIHN1cnZleWVkIHNldmVyYWwgcm91dGVzIChjYW5kaWRhdGUgcm9hZCBiZXR3ZWVuIGFueSB0d28gY2l0aWVzKS4gRWFjaCByb3V0ZSBpcyBhIGJpZGlyZWN0aW9uYWwgY29ubmVjdGlvbiBiZXR3ZWVuIHR3byBjaXRpZXMuIEhlIGNhbiBidWlsZCBhIGJpLWRpcmVjdGlvbmFsIHJvYWQgb24gdGhlIHN1cnZleWVkIHJvdXRlIGZvciBhIHNwZWNpZmljIGNvc3QgKFRoZSBzaG9ydGVyIHRoZSByb3V0ZSBpcyB0aGUgY2hlYXBlciB0aGUgcm9hZCkuPFwvcD5cclxuXHJcbjxwPlRoaXMgZW5naW5lZXIgaGFzIG5ldmVyIHBsYW5uZWQgYSByb2FkIHN5c3RlbSBpbiBhZHZhbmNlLiBIZSB3b3VsZCBqdXN0IHBpY2sgb25lIG9mIHRoZSByb3V0ZXMgYmFzZWQgb24gaGlzIHByZWZlcmVuY2UsIGFuZCBidWlsZCBhIHJvYWQgdW50aWwgYWxsIHRoZSBjaXRpZXMgYXJlIGNvbm5lY3RlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+UmlnaHQgbm93IHRoaXMgZW5naW5lZXIgaXMgZ29pbmcgdG8gYnVpbGQgYSByb2FkIGZyb20gdGhlIGNpdHkgcCB0byB0aGUgY2l0eSBxLiBXaXRoIHByZXNzdXJlIGZyb20gdGhlIGdvdmVybm1lbnQgdG8gcmVkdWNlIHRoZSBjb3N0LCBoZSBhc2tzIHlvdSB0byB3cml0ZSBhIHByb2dyYW0gdG8gZGVjaWRlLCBpZiBoZSBzaG91bGQgYnVpbGQgdGhpcyByb2FkIG9yIG5vdC4gWW91ciBwcm9ncmFtIHNob3VsZCBzYXkgeWVzIGlmIHRoZSBidWlsZGluZyBvZiB0aGlzIHJvYWQgZ3VhcmFudGVlZCB0aGF0IGl0IGNhbiBiZSBwYXJ0IG9mIHRoZSBzaG9ydGVzdCByb2FkIHN5c3RlbSB0aGF0IGNvbm5lY3RzIGFsbCBjaXRpZXMgdG9nZXRoZXIuIE90aGVyd2lzZSwgeW91ciBwcm9ncmFtIHNob3VsZCBzYXkgbm8uJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIG9mIGlucHV0IGlzIGEgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCAmbGU7IDEwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIHRlc3QgY2FzZSBzdGFydCB3aXRoIGEgbGluZSBjb250YWlucyA0IGludGVnZXJzIE4sIE0sIHAsIGFuZCBxLiBOICgyICZsZTsgTiAmbGU7IDEwIDAwMCkgaXMgdGhlIG51bWJlciBvZiBjaXRpZXMgaW4gdGhpcyByb2FkIHN5c3RlbS4gTSAoMSAmbGU7IE0gJmxlOyAyMCAwMDApIGlzIHRoZSBudW1iZXIgb2Ygc3VydmV5ZWQgcm91dGVzLiBwIGFuZCBxICgxICZsZTsgcCAmbGU7IE4gYW5kIDEgJmxlOyBxICZsZTsgTikgaW5kaWNhdGUgdGhlIHJvdXRlIGJldHdlZW4gdHdvIGNpdGllcywgdGhhdCB0aGUgZW5naW5lZXIgYXNrcyBpZiBoZSBjYW4gYnVpbGQgYSByb2FkIG9yIG5vdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlbiwgdGhlIGVhY2ggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIDMgbnVtYmVycyB1LCB2LCBhbmQgdyAoMSAmbGU7IHUgJmxlOyBOLCAxICZsZTsgdiAmbGU7IE4sIDEgJmxlOyB3ICZsZTsgNDAwIDAwMCkgaW5kaWNhdGVzIHRoYXQgdGhlcmUgYXJlIHRoZSBiaWRpcmVjdGlvbmFsIHJvdXRlIG9mIGxlbmd0aCB3IGJldHdlZW4gdSBhbmQgdi4gVGhlIGxlbmd0aCBvZiBlYWNoIHJvYWQgaW4gdGhlIGN1cnJlbnQgc3lzdGVtIGlzIHVuaXF1ZS4gQW5kLCB0aGVyZSBpcyBvbmx5IG9uZSBwb3NzaWJsZSByb2FkIGJldHdlZW4gdHdvIGNpdGllcy4gVGhlIGlucHV0IGd1YXJhbnRlZXMgdGhhdCBhdCBsZWFzdCBvbmUgcm9hZCBzeXN0ZW0gaGFzIGEgcm91dGUgYmV0d2VlbiBhbnkgdHdvIGNpdGllcy4gQWxsIG51bWJlcnMgYXJlIGludGVnZXI8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIGRpc3BsYXkgWUVTIGlmIHRoZSBlbmdpbmVlciBjYW4gYnVpbGQgYSByb2FkIHAtcSBhcyBwYXJ0IG9mIHRoZSBzaG9ydGVzdCByb2FkIHN5c3RlbS4gT3RoZXJ3aXNlLCBwcmludCBOTy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=