문제
맨체스터에 있는 도로는 모두 일방 통행이다. 또한 이 도로는 모두 1시간에 지나갈 수 있는 차의 개수 제한이 있다. 길(경로)에도 차의 개수 제한이 있는데, 이것은 이 길에 있는 도로의 제한 중 최솟값이다.
A에서 B로 가는 중복 비율은 A에서 B로 가는 모든 길을 동시에 이용했을 때 1시간 동안 B에 도착할 수 있는 차의 최대 개수와 길 1개를 이용했을 때 도착할 수 있는 최대 개수의 비율이다.
최소 중복 비율은 길 1개를 이용했을 때 도착할 수 있는 최대 개수가 가장 큰 값이 된다.
맨체스터의 도로 정보와 A, B가 주어졌을 때, 최소 중복 비율을 구하는 프로그램을 작성하시오.
출력
각 테스트 케이스에 대해 최소 중복 비율을 소수점 셋째자리까지 출력한다.
W3sicHJvYmxlbV9pZCI6IjI2NzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5ZThcdWNjYjRcdWMyYTRcdWQxMzBcdWM3NTggXHViM2M0XHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI5ZThcdWNjYjRcdWMyYTRcdWQxMzBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjNjNFx1Yjg1Y1x1YjI5NCBcdWJhYThcdWI0NTAgXHVjNzdjXHViYzI5IFx1ZDFiNVx1ZDU4OVx1Yzc3NFx1YjJlNC4gXHViNjEwXHVkNTVjIFx1Yzc3NCBcdWIzYzRcdWI4NWNcdWIyOTQgXHViYWE4XHViNDUwIDFcdWMyZGNcdWFjMDRcdWM1ZDAgXHVjOWMwXHViMDk4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjYzI4XHVjNzU4IFx1YWMxY1x1YzIxOCBcdWM4MWNcdWQ1NWNcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFlMzgoXHVhY2JkXHViODVjKVx1YzVkMFx1YjNjNCBcdWNjMjhcdWM3NTggXHVhYzFjXHVjMjE4IFx1YzgxY1x1ZDU1Y1x1Yzc3NCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1Yzc3NFx1YWM4M1x1Yzc0MCBcdWM3NzQgXHVhZTM4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIzYzRcdWI4NWNcdWM3NTggXHVjODFjXHVkNTVjIFx1YzkxMSBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkFcdWM1ZDBcdWMxMWMgQlx1Yjg1YyBcdWFjMDBcdWIyOTQgXHVjOTExXHViY2Y1IFx1YmU0NFx1YzcyOFx1Yzc0MCBBXHVjNWQwXHVjMTFjIEJcdWI4NWMgXHVhYzAwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWFlMzhcdWM3NDQgXHViM2Q5XHVjMmRjXHVjNWQwIFx1Yzc3NFx1YzZhOVx1ZDU4OFx1Yzc0NCBcdWI1NGMgMVx1YzJkY1x1YWMwNCBcdWIzZDlcdWM1NDggQlx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNjMjhcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1YzY0MCBcdWFlMzggMVx1YWMxY1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1ODhcdWM3NDQgXHViNTRjIFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWM3NTggXHViZTQ0XHVjNzI4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNkNWNcdWMxOGMgXHVjOTExXHViY2Y1IFx1YmU0NFx1YzcyOFx1Yzc0MCBcdWFlMzggMVx1YWMxY1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1ODhcdWM3NDQgXHViNTRjIFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWFjMDAgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjMTJcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5ZThcdWNjYjRcdWMyYTRcdWQxMzBcdWM3NTggXHViM2M0XHViODVjIFx1YzgxNVx1YmNmNFx1YzY0MCBBLCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Y2Q1Y1x1YzE4YyBcdWM5MTFcdWJjZjUgXHViZTQ0XHVjNzI4XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUICgxICZsZTsgVCAmbGU7IDEsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggNFx1YWMxY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBOLCBFLCBBLCBCXHVjNzc0XHViMmU0LiBOICgyICZsZTsgTiAmbGU7IDEsMDAwKVx1Yzc0MCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHVjODE1XHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCwgRSAoRSAmZ2U7IDEpXHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuIEEgKDAgJmxlOyBBICZsdDsgTilcdWM2NDAgQiAoMCAmbGU7IEIgJmx0OyBOLCBBICZuZTsgQilcdWIyOTQgXHViYjM4XHVjODFjIFx1YzEyNFx1YmE4NVx1YzVkMCBcdWIwOThcdWM2NDBcdWM3ODhcdWIyOTQgQVx1YzY0MCBCXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHViMmU0XHVjNzRjIEVcdWFjMWMgXHVjOTA0XHVjNzQwIFx1YWMwMSBcdWFjMDRcdWMxMjBcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YzgxNVx1YmNmNFx1YjI5NCBVIFYgV1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0XHViMzcwLCBVICgwICZsZTsgVSAmbHQ7IE4pXHVjNjQwIFYgKDAgJmxlOyBWICZsdDsgTiwgViAmbmU7IFUpXHViMjk0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NzRcdWFjZTAsIFcgKDEgJmxlOyBXICZsZTsgMTAwMClcdWIyOTQgVVx1YzVkMFx1YzExYyBWXHViODVjIFx1ZDVhNVx1ZDU1OFx1YjI5NCBcdWIzYzRcdWI4NWNcdWM3NTggMVx1YzJkY1x1YWMwNFx1YzVkMCBcdWM5YzBcdWIwOThcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNjMjhcdWM3NTggXHVhYzFjXHVjMjE4IFx1YzgxY1x1ZDU1Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjZDVjXHVjMThjIFx1YzkxMVx1YmNmNSBcdWJlNDRcdWM3MjhcdWM3NDQgXHVjMThjXHVjMjE4XHVjODEwIFx1YzE0Ylx1YzlmOFx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjY3OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJvdXRlIFJlZHVuZGFuY3kiLCJkZXNjcmlwdGlvbiI6IjxwPkEgY2l0eSBpcyBtYWRlIHVwIGV4Y2x1c2l2ZWx5IG9mIG9uZS13YXkgc3RyZWV0cy4gRWFjaCBzdHJlZXQgaW4gdGhlIGNpdHkgaGFzIGEgY2FwYWNpdHksIHRoZSBtYXhpbXVtIG51bWJlciBvZiBjYXJzIGl0IGNhbiBjYXJyeSBwZXIgaG91ci4gQW55IHJvdXRlIChwYXRoKSBhbHNvIGhhcyBhIGNhcGFjaXR5LCB3aGljaCBpcyB0aGUgbWluaW11bSBvZiB0aGUgY2FwYWNpdGllcyBvZiB0aGUgc3RyZWV0cyBhbG9uZyB0aGF0IHJvdXRlLjxcL3A+XHJcblxyXG48cD5UaGUgcmVkdW5kYW5jeSByYXRpbyBmcm9tIHBvaW50IEEgdG8gcG9pbnQgQiBpcyB0aGUgcmF0aW8gb2YgdGhlIG1heGltdW0gbnVtYmVyIG9mIGNhcnMgdGhhdCBjYW4gZ2V0IGZyb20gQSB0byBCIGluIGFuIGhvdXIgdXNpbmcgYWxsIHJvdXRlcyBzaW11bHRhbmVvdXNseSwgdG8gdGhlIG1heGltdW0gbnVtYmVyIG9mIGNhcnMgdGhhdCBjYW4gZ2V0IGZyb20gQSB0byBCIGluIGFuIGhvdXIgdXNpbmcganVzdCBvbmUgcm91dGUuIFRoZSBtaW5pbXVtIHJlZHVuZGFuY3kgcmF0aW8gaXMgdGhlIG51bWJlciBvZiBjYXJzIHRoYXQgY2FuIGdldCBmcm9tIEEgdG8gQiBpbiBhbiBob3VyIHVzaW5nIGFsbCBwb3NzaWJsZSByb3V0ZXMgc2ltdWx0YW5lb3VzbHksIGRpdmlkZWQgYnkgdGhlIGNhcGFjaXR5IG9mIHRoZSBzaW5nbGUgcm91dGUgd2l0aCB0aGUgbGFyZ2VzdCBjYXBhY2l0eS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgUCwgKDEgJmxlOyBQICZsZTsgMTAwMCksIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZGF0YSBzZXRzIHRoYXQgZm9sbG93LiBFYWNoIGRhdGEgc2V0IGNvbnNpc3RzIG9mIHNldmVyYWwgbGluZXMgYW5kIHJlcHJlc2VudHMgYSBkaXJlY3RlZCBncmFwaCB3aXRoIHBvc2l0aXZlIGludGVnZXIgd2VpZ2h0cy48XC9wPlxyXG5cclxuPHA+VGhlIGZpcnN0IGxpbmUgb2YgZWFjaCBkYXRhIHNldCBjb250YWlucyBmaXZlIHNwYWNlIHNlcGFyYXRlZCBpbnRlZ2Vycy4gVGhlIGZpcnN0IGludGVnZXIsIEQgaXMgdGhlIGRhdGEgc2V0IG51bWJlci4gVGhlIHNlY29uZCBpbnRlZ2VyLCBOICgyICZsZTsgTiAmbGU7IDEwMDApLCBpcyB0aGUgbnVtYmVyIG9mIG5vZGVzIGluIHRoZSBncmFwaC4gVGhlIHRoaXJkIGludGVnZXIsIEUsIChFICZnZTsgMSksIGlzIHRoZSBudW1iZXIgb2YgZWRnZXMgaW4gdGhlIGdyYXBoLiBUaGUgZm91cnRoIGludGVnZXIsIEEsICgwICZsZTsgQSAmbHQ7IE4pLCBpcyB0aGUgaW5kZXggb2YgcG9pbnQgQS4gVGhlIGZpZnRoIGludGVnZXIsIEIsICgwICZsZTsgQiAmbHQ7IE4sIEEgJm5lOyBCKSwgaXMgdGhlIGluZGV4IG9mIHBvaW50IEIuPFwvcD5cclxuXHJcbjxwPlRoZSByZW1haW5pbmcgRSBsaW5lcyBkZXNjcmliZSBlYWNoIGVkZ2UuIEVhY2ggbGluZSBjb250YWlucyB0aHJlZSBzcGFjZSBzZXBhcmF0ZWQgaW50ZWdlcnMuIFRoZSBmaXJzdCBpbnRlZ2VyLCBVICgwICZsZTsgVSAmbHQ7IE4pLCBpcyB0aGUgaW5kZXggb2Ygbm9kZSBVLiBUaGUgc2Vjb25kIGludGVnZXIsIFYgKDAgJmxlOyBWICZsdDsgTiwgViAmbmU7IFUpLCBpcyB0aGUgaW5kZXggb2Ygbm9kZSBWLiBUaGUgdGhpcmQgaW50ZWdlciwgVyAoMSAmbGU7IFcgJmxlOyAxMDAwKSwgaXMgdGhlIGNhcGFjaXR5ICh3ZWlnaHQpIG9mIHRoZSBwYXRoIGZyb20gVSB0byBWLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0IHRoZXJlIGlzIG9uZSBsaW5lIG9mIG91dHB1dC4gSXQgY29udGFpbnMgdGhlIGRhdGEgc2V0IG51bWJlciAoTikgZm9sbG93ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIGZvbGxvd2VkIGJ5IGEgZmxvYXRpbmctcG9pbnQgdmFsdWUgd2hpY2ggaXMgdGhlIG1pbmltdW0gcmVkdW5kYW5jeSByYXRpbyB0byAzIGRpZ2l0cyBhZnRlciB0aGUgZGVjaW1hbCBwb2ludC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d