시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 17 12 11 68.750%

문제

맨체스터에 있는 도로는 모두 일방 통행이다. 또한 이 도로는 모두 1시간에 지나갈 수 있는 차의 개수 제한이 있다. 길(경로)에도 차의 개수 제한이 있는데, 이것은 이 길에 있는 도로의 제한 중 최소값이다.

A에서 B로 가는 중복 비율은 A에서 B로 가는 모든 길을 동시에 이용했을 때 1시간 동안 B에 도착할 수 있는 차의 최대 개수와 길 1개를 이용했을 때 도착할 수 있는 최대 개수의 비율이다.

최소 중복 비율은 길 1개를 이용했을 때 도착할 수 있는 최대 개수가 가장 큰 값이 된다.

맨체스터의 도로 정보와 A, B가 주어졌을 때, 최소 중복 비율을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어 있다.

첫째 줄에 정수 4개가 주어진다. 차례대로 N, E, A, B이다. N(2 <= N <= 1,000)은 그래프의 정점의 개수, E(E>=1)는 간선의 개수이다. A(0<=A<N)와 B(0<=B<N, A!=B)는 문제 설명에 나와있는 A와 B이다.

그 다음 E개 줄은 각 간선에 대한 정보이다. 이 정보는 U V W로 구성되어 있는데, U와 V는 그래프의 정점이고, W는 U에서 V로 향하는 도로의 1시간에 지나갈 수 있는 차의 개수 제한이다.

출력

각 테스트 케이스에 대해 최소 중복 비율을 소수점 셋째자리까지 출력한다. 

예제 입력 1

1
7 11 0 6
0 1 3
0 3 3
1 2 4
2 0 3
2 3 1
2 4 2
3 4 2
3 5 6
4 1 1
4 6 1
5 6 9

예제 출력 1

1.667
W3sicHJvYmxlbV9pZCI6IjI2NzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5ZThcdWNjYjRcdWMyYTRcdWQxMzBcdWM3NTggXHViM2M0XHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWI5ZThcdWNjYjRcdWMyYTRcdWQxMzBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjNjNFx1Yjg1Y1x1YjI5NCBcdWJhYThcdWI0NTAgXHVjNzdjXHViYzI5IFx1ZDFiNVx1ZDU4OVx1Yzc3NFx1YjJlNC4gXHViNjEwXHVkNTVjIFx1Yzc3NCBcdWIzYzRcdWI4NWNcdWIyOTQgXHViYWE4XHViNDUwIDFcdWMyZGNcdWFjMDRcdWM1ZDAgXHVjOWMwXHViMDk4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjYzI4XHVjNzU4IFx1YWMxY1x1YzIxOCBcdWM4MWNcdWQ1NWNcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFlMzgoXHVhY2JkXHViODVjKVx1YzVkMFx1YjNjNCBcdWNjMjhcdWM3NTggXHVhYzFjXHVjMjE4IFx1YzgxY1x1ZDU1Y1x1Yzc3NCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1Yzc3NFx1YWM4M1x1Yzc0MCBcdWM3NzQgXHVhZTM4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIzYzRcdWI4NWNcdWM3NTggXHVjODFjXHVkNTVjIFx1YzkxMSBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdEFcdWM1ZDBcdWMxMWMgQlx1Yjg1YyBcdWFjMDBcdWIyOTQgXHVjOTExXHViY2Y1IFx1YmU0NFx1YzcyOFx1Yzc0MCBBXHVjNWQwXHVjMTFjIEJcdWI4NWMgXHVhYzAwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWFlMzhcdWM3NDQgXHViM2Q5XHVjMmRjXHVjNWQwIFx1Yzc3NFx1YzZhOVx1ZDU4OFx1Yzc0NCBcdWI1NGMgMVx1YzJkY1x1YWMwNCBcdWIzZDlcdWM1NDggQlx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNjMjhcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1YzY0MCBcdWFlMzggMVx1YWMxY1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1ODhcdWM3NDQgXHViNTRjIFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWM3NTggXHViZTQ0XHVjNzI4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWNkNWNcdWMxOGMgXHVjOTExXHViY2Y1IFx1YmU0NFx1YzcyOFx1Yzc0MCBcdWFlMzggMVx1YWMxY1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1ODhcdWM3NDQgXHViNTRjIFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWFjMDAgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjMTJcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI5ZThcdWNjYjRcdWMyYTRcdWQxMzBcdWM3NTggXHViM2M0XHViODVjIFx1YzgxNVx1YmNmNFx1YzY0MCBBLCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Y2Q1Y1x1YzE4YyBcdWM5MTFcdWJjZjUgXHViZTQ0XHVjNzI4XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUKDEgJmx0Oz0gVCAmbHQ7PSAxLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4IDRcdWFjMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgTiwgRSwgQSwgQlx1Yzc3NFx1YjJlNC4gTigyICZsdDs9IE4gJmx0Oz0gMSwwMDApXHVjNzQwIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4LCBFKEUmZ3Q7PTEpXHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuIEEoMCZsdDs9QSZsdDtOKVx1YzY0MCBCKDAmbHQ7PUImbHQ7TiwgQSE9QilcdWIyOTQgXHViYjM4XHVjODFjIFx1YzEyNFx1YmE4NVx1YzVkMCBcdWIwOThcdWM2NDBcdWM3ODhcdWIyOTQgQVx1YzY0MCBCXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWFkZjggXHViMmU0XHVjNzRjIEVcdWFjMWMgXHVjOTA0XHVjNzQwIFx1YWMwMSBcdWFjMDRcdWMxMjBcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YzgxNVx1YmNmNFx1YjI5NCBVIFYgV1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0XHViMzcwLCBVXHVjNjQwIFZcdWIyOTQgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YzgxNVx1YzgxMFx1Yzc3NFx1YWNlMCwgV1x1YjI5NCBVXHVjNWQwXHVjMTFjIFZcdWI4NWMgXHVkNWE1XHVkNTU4XHViMjk0IFx1YjNjNFx1Yjg1Y1x1Yzc1OCAxXHVjMmRjXHVhYzA0XHVjNWQwIFx1YzljMFx1YjA5OFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2MyOFx1Yzc1OCBcdWFjMWNcdWMyMTggXHVjODFjXHVkNTVjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjZDVjXHVjMThjIFx1YzkxMVx1YmNmNSBcdWJlNDRcdWM3MjhcdWM3NDQgXHVjMThjXHVjMjE4XHVjODEwIFx1YzE0Ylx1YzlmOFx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjY3OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJvdXRlIFJlZHVuZGFuY3kiLCJkZXNjcmlwdGlvbiI6IjxwPkEgY2l0eSBpcyBtYWRlIHVwIGV4Y2x1c2l2ZWx5IG9mIG9uZS13YXkgc3RyZWV0cy4gRWFjaCBzdHJlZXQgaW4gdGhlIGNpdHkgaGFzIGEgY2FwYWNpdHksIHRoZSBtYXhpbXVtIG51bWJlciBvZiBjYXJzIGl0IGNhbiBjYXJyeSBwZXIgaG91ci4gQW55IHJvdXRlIChwYXRoKSBhbHNvIGhhcyBhIGNhcGFjaXR5LCB3aGljaCBpcyB0aGUgbWluaW11bSBvZiB0aGUgY2FwYWNpdGllcyBvZiB0aGUgc3RyZWV0cyBhbG9uZyB0aGF0IHJvdXRlLjxcL3A+XHJcblxyXG48cD5UaGUgcmVkdW5kYW5jeSByYXRpbyBmcm9tIHBvaW50IEEgdG8gcG9pbnQgQiBpcyB0aGUgcmF0aW8gb2YgdGhlIG1heGltdW0gbnVtYmVyIG9mIGNhcnMgdGhhdCBjYW4gZ2V0IGZyb20gQSB0byBCIGluIGFuIGhvdXIgdXNpbmcgYWxsIHJvdXRlcyBzaW11bHRhbmVvdXNseSwgdG8gdGhlIG1heGltdW0gbnVtYmVyIG9mIGNhcnMgdGhhdCBjYW4gZ2V0IGZyb20gQSB0byBCIGluIGFuIGhvdXIgdXNpbmcganVzdCBvbmUgcm91dGUuIFRoZSBtaW5pbXVtIHJlZHVuZGFuY3kgcmF0aW8gaXMgdGhlIG51bWJlciBvZiBjYXJzIHRoYXQgY2FuIGdldCBmcm9tIEEgdG8gQiBpbiBhbiBob3VyIHVzaW5nIGFsbCBwb3NzaWJsZSByb3V0ZXMgc2ltdWx0YW5lb3VzbHksIGRpdmlkZWQgYnkgdGhlIGNhcGFjaXR5IG9mIHRoZSBzaW5nbGUgcm91dGUgd2l0aCB0aGUgbGFyZ2VzdCBjYXBhY2l0eS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgUCwgKCAxICZsZTsgUCAmbGU7IDEwMDApLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGEgc2V0cyB0aGF0IGZvbGxvdy4gRWFjaCBkYXRhIHNldCBjb25zaXN0cyBvZiBzZXZlcmFsIGxpbmVzIGFuZCByZXByZXNlbnRzIGEgZGlyZWN0ZWQgZ3JhcGggd2l0aCBwb3NpdGl2ZSBpbnRlZ2VyIHdlaWdodHMuPFwvcD5cclxuXHJcbjxwPlRoZSBmaXJzdCBsaW5lIG9mIGVhY2ggZGF0YSBzZXQgY29udGFpbnMgZml2ZSBzcGFjZSBzZXBhcmF0ZWQgaW50ZWdlcnMuIFRoZSBmaXJzdCBpbnRlZ2VyLCBEIGlzIHRoZSBkYXRhIHNldCBudW1iZXIuIFRoZSBzZWNvbmQgaW50ZWdlciwgTiAoIDIgJmxlOyBOICZsZTsgMTAwMCksIGlzIHRoZSBudW1iZXIgb2Ygbm9kZXMgaW4gdGhlIGdyYXBoLiBUaGUgdGhpcmQgaW50ZWdlciwgRSwgKEUgJmd0OyAxKSwgaXMgdGhlIG51bWJlciBvZiBlZGdlcyBpbiB0aGUgZ3JhcGguIFRoZSBmb3VydGggaW50ZWdlciwgQSwgKCAwICZsZTsgQSAmbHQ7IE4pLCBpcyB0aGUgaW5kZXggb2YgcG9pbnQgQS4gVGhlIGZpZnRoIGludGVnZXIsIEIsICggMCAmbGU7IEIgJmx0OyBOLCBBICZuZTsgQiksIGlzIHRoZSBpbmRleCBvZiBwb2ludCBCLjxcL3A+XHJcblxyXG48cD5UaGUgcmVtYWluaW5nIEUgbGluZXMgZGVzY3JpYmUgZWFjaCBlZGdlLiBFYWNoIGxpbmUgY29udGFpbnMgdGhyZWUgc3BhY2Ugc2VwYXJhdGVkIGludGVnZXJzLiBUaGUgZmlyc3QgaW50ZWdlciwgVSAoIDAgJmxlOyBVICZsdDsgTiksIGlzIHRoZSBpbmRleCBvZiBub2RlIFUuIFRoZSBzZWNvbmQgaW50ZWdlciwgViAoIDAgJmxlOyBWICZsdDsgTiwgViAmbmU7IFUpLCBpcyB0aGUgaW5kZXggb2Ygbm9kZSBWLiBUaGUgdGhpcmQgaW50ZWdlciwgVyAoIDEgJmxlOyBXICZsdDsgMTAwMCksIGlzIHRoZSBjYXBhY2l0eSAod2VpZ2h0KSBvZiB0aGUgcGF0aCBmcm9tIFUgdG8gVi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCB0aGVyZSBpcyBvbmUgbGluZSBvZiBvdXRwdXQuIEl0IGNvbnRhaW5zIHRoZSBkYXRhIHNldCBudW1iZXIgKE4pIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIHNwYWNlLCBmb2xsb3dlZCBieSBhIGZsb2F0aW5nLXBvaW50IHZhbHVlIHdoaWNoIGlzIHRoZSBtaW5pbXVtIHJlZHVuZGFuY3kgcmF0aW8gdG8gMyBkaWdpdHMgYWZ0ZXIgdGhlIGRlY2ltYWwgcG9pbnQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d