시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3 1 1 33.333%

문제

어드벤처 게임을 하던 중, 1부터 n까지의 번호가 붙은 방을 지나가야 하는 마법의 미로를 마주쳤다. 각 방 안에는 번호가 붙은 문이 있을 수 있고, 각 문은 해당하는 번호의 방으로 통한다. 방 안에는 레프리콘이나 트롤이 있을 수도 있다.

레프리콘이 있는 방에 들어가면 레프리콘은 모험가의 소지금이 일정 양 이하로 떨어지지 않게 채워준다. 레프리콘은 모험가의 소지금이 일정량 미만일 때에는 그만한 양이 되도록 금화를 채워주고, 소지금이 일정량 이상일 때에는 그대로 둔다. 트롤이 있는 방에 들어가면 일정량의 통행료를 지불해야만 지나갈 수 있다.

모험가는 소지금이 0인 상태에서 출발한다. 과연 모험가는 1번방에서 출발해서 n번방에 도착할 수 있을까? n번방에 트롤이 있는 경우에도 통행료를 지불해야만 미로를 통과할 수 있다.

입력

입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타내는 알파벳 하나(E: 빈 방, L: 레프리콘, T: 트롤)와 그 방의 레프리콘이나 트롤이 정해놓은 금액(빈 방일 경우 0이다.), 그리고 그 방에서 다른 방으로 갈 수 있는 문의 번호들로 이루어진다. 각 줄은 0으로 끝난다. 미로의 방 수가 0개인 입력이 들어오면 입력을 종료한다.

출력

출력은 각 미로마다 한 줄씩으로 이루어진다. 각 줄에는 1번방에서 출구까지 갈 수 있는지를 "Yes" 또는 "No"로 출력한다.

예제 입력 1

3
E 0 2 0
L 10 3 0
T 15 1 2 0
4
E 0 2 3 0
L 201 2 3 0
L 10 4 0
T 15 2 3 1 0
0

예제 출력 1

No
Yes

힌트

W3sicHJvYmxlbV9pZCI6IjIzMTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1YjRcdWI0ZGNcdWJjYTRcdWNjOTggXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWI0ZGNcdWJjYTRcdWNjOTggXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YjM1OCBcdWM5MTEsIDFcdWJkODBcdWQxMzAgblx1YWU0Y1x1YzljMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNzQwIFx1YmMyOVx1Yzc0NCBcdWM5YzBcdWIwOThcdWFjMDBcdWM1N2MgXHVkNTU4XHViMjk0IFx1YjljOFx1YmM5NVx1Yzc1OCBcdWJiZjhcdWI4NWNcdWI5N2MgXHViOWM4XHVjOGZjXHVjY2U0XHViMmU0LiBcdWFjMDEgXHViYzI5IFx1YzU0OFx1YzVkMFx1YjI5NCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNzQwIFx1YmIzOFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1YmIzOFx1Yzc0MCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHViYzg4XHVkNjM4XHVjNzU4IFx1YmMyOVx1YzczY1x1Yjg1YyBcdWQxYjVcdWQ1NWNcdWIyZTQuIFx1YmMyOSBcdWM1NDhcdWM1ZDBcdWIyOTQgXHViODA4XHVkNTA0XHViOWFjXHVjZjU4XHVjNzc0XHViMDk4IFx1ZDJiOFx1Yjg2NFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViODA4XHVkNTA0XHViOWFjXHVjZjU4XHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWM1ZDAgXHViNGU0XHVjNWI0XHVhYzAwXHViYTc0IFx1YjgwOFx1ZDUwNFx1YjlhY1x1Y2Y1OFx1Yzc0MCBcdWJhYThcdWQ1ZDhcdWFjMDBcdWM3NTggXHVjMThjXHVjOWMwXHVhZTA4XHVjNzc0IFx1Yzc3Y1x1YzgxNSBcdWM1OTEgXHVjNzc0XHVkNTU4XHViODVjIFx1YjVhOFx1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWFjOGMgXHVjYzQ0XHVjNmNjXHVjOTAwXHViMmU0LiBcdWI4MDhcdWQ1MDRcdWI5YWNcdWNmNThcdWM3NDAgXHViYWE4XHVkNWQ4XHVhYzAwXHVjNzU4IFx1YzE4Y1x1YzljMFx1YWUwOFx1Yzc3NCBcdWM3N2NcdWM4MTVcdWI3YzkgXHViYmY4XHViOWNjXHVjNzdjIFx1YjU0Y1x1YzVkMFx1YjI5NCBcdWFkZjhcdWI5Y2NcdWQ1NWMgXHVjNTkxXHVjNzc0IFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWFlMDhcdWQ2NTRcdWI5N2MgXHVjYzQ0XHVjNmNjXHVjOGZjXHVhY2UwLCBcdWMxOGNcdWM5YzBcdWFlMDhcdWM3NzQgXHVjNzdjXHVjODE1XHViN2M5IFx1Yzc3NFx1YzBjMVx1Yzc3YyBcdWI1NGNcdWM1ZDBcdWIyOTQgXHVhZGY4XHViMzAwXHViODVjIFx1YjQ1NFx1YjJlNC4gXHVkMmI4XHViODY0XHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWM1ZDAgXHViNGU0XHVjNWI0XHVhYzAwXHViYTc0IFx1Yzc3Y1x1YzgxNVx1YjdjOVx1Yzc1OCBcdWQxYjVcdWQ1ODlcdWI4Y2NcdWI5N2MgXHVjOWMwXHViZDg4XHVkNTc0XHVjNTdjXHViOWNjIFx1YzljMFx1YjA5OFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWQ1ZDhcdWFjMDBcdWIyOTQgXHVjMThjXHVjOWMwXHVhZTA4XHVjNzc0IDBcdWM3NzggXHVjMGMxXHVkMGRjXHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU1Y1x1YjJlNC4gXHVhY2ZjXHVjNWYwIFx1YmFhOFx1ZDVkOFx1YWMwMFx1YjI5NCAxXHViYzg4XHViYzI5XHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU3NFx1YzExYyBuXHViYzg4XHViYzI5XHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjPyBuXHViYzg4XHViYzI5XHVjNWQwIFx1ZDJiOFx1Yjg2NFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViM2M0IFx1ZDFiNVx1ZDU4OVx1YjhjY1x1Yjk3YyBcdWM5YzBcdWJkODhcdWQ1NzRcdWM1N2NcdWI5Y2MgXHViYmY4XHViODVjXHViOTdjIFx1ZDFiNVx1YWNmY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHViYmY4XHViODVjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YmJmOFx1Yjg1Y1x1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmJmOFx1Yjg1Y1x1Yzc1OCBcdWJjMjkgXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMTggbigxICZsZTsgbiAmbGU7IDEwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIG4gXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWJjMjlcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YmMyOVx1Yzc1OCBcdWM4MTVcdWJjZjRcdWIyOTQgXHViYzI5XHVjNzU4IFx1YjBiNFx1YzZhOVx1YmIzY1x1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1ZDU1OFx1YjA5OChFOiBcdWJlNDggXHViYzI5LCBMOiBcdWI4MDhcdWQ1MDRcdWI5YWNcdWNmNTgsIFQ6IFx1ZDJiOFx1Yjg2NClcdWM2NDAgXHVhZGY4IFx1YmMyOVx1Yzc1OCBcdWI4MDhcdWQ1MDRcdWI5YWNcdWNmNThcdWM3NzRcdWIwOTggXHVkMmI4XHViODY0XHVjNzc0IFx1YzgxNVx1ZDU3NFx1YjE5M1x1Yzc0MCBcdWFlMDhcdWM1NjEoXHViZTQ4IFx1YmMyOVx1Yzc3YyBcdWFjYmRcdWM2YjAgMFx1Yzc3NFx1YjJlNC4pLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhZGY4IFx1YmMyOVx1YzVkMFx1YzExYyBcdWIyZTRcdWI5NzggXHViYzI5XHVjNzNjXHViODVjIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmIzOFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI0ZTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNzQwIDBcdWM3M2NcdWI4NWMgXHViMDVkXHViMDljXHViMmU0LiBcdWJiZjhcdWI4NWNcdWM3NTggXHViYzI5IFx1YzIxOFx1YWMwMCAwXHVhYzFjXHVjNzc4IFx1Yzc4NVx1YjgyNVx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM2MjRcdWJhNzQgXHVjNzg1XHViODI1XHVjNzQ0IFx1Yzg4NVx1YjhjY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkOWNcdWI4MjVcdWM3NDAgXHVhYzAxIFx1YmJmOFx1Yjg1Y1x1YjljOFx1YjJlNCBcdWQ1NWMgXHVjOTA0XHVjNTI5XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCAxXHViYzg4XHViYzI5XHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YWQ2Y1x1YWU0Y1x1YzljMCBcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMFx1Yjk3YyAmcXVvdDtZZXMmcXVvdDsgXHViNjEwXHViMjk0ICZxdW90O05vJnF1b3Q7XHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMzEwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQWR2ZW50dXJlIEdhbWUiLCJkZXNjcmlwdGlvbiI6IjxwPlBhcnQgb2YgYW4gYWR2ZW50dXJlIGdhbWUgcmVxdWlyZXMgdGhlIGFkdmVudHVyZXIgdG8gbWFrZSBoZXIgd2F5IHRocm91Z2ggYSBtYWdpY2FsIG1hemUgb2YgbnVtYmVyZWQgcm9vbXMuIEVhY2ggcm9vbSBoYXMgYSBzZXQgb2YgbnVtYmVyZWQgZG9vcnMgdGhhdCBsZWFkIHRvIHRoZSBpbmRpY2F0ZWQgcm9vbXMuIEFkZGl0aW9uYWxseSwgZWFjaCByb29tIG1pZ2h0IGNvbnRhaW4gZWl0aGVyIGEgbGVwcmVjaGF1biBvciBhIHRyb2xsLjxcL3A+XHJcblxyXG48cD5XaGVuZXZlciB0aGUgYWR2ZW50dXJlciB2aXNpdHMgYSByb29tIGNvbnRhaW5pbmcgYSBsZXByZWNoYXVuLCB0aGUgbGVwcmVjaGF1biB3aWxsIGVuc3VyZSB0aGF0IHNoZSBsZWF2ZXMgd2l0aCBhdCBsZWFzdCBhIGNlcnRhaW4gbnVtYmVyIG9mIGdvbGQgcGllY2VzIChHUCkgaW4gaGVyIHNhY2suIFRoYXQgaXMsIGlmIHNoZSBhcnJpdmVzIHdpdGggZmV3ZXIgR1AgdGhhbiB0aGUgcHJlc2NyaWJlZCBhbW91bnQsIHRoZW4gdGhlIGxlcHJlY2hhdW4gd2lsbCAmbGRxdW87dG9wIGhlciB1cCZyZHF1bzsgdG8gdGhhdCBhbW91bnQ7IGhvd2V2ZXIsIGlmIHNoZSBhcnJpdmVzIHdpdGggdGhlIHByZXNjcmliZWQgYW1vdW50IG9yIG1vcmUsIHRoZW4gaGVyIHN1cHBseSBvZiBHUCB3aWxsIHJlbWFpbiB1bmNoYW5nZWQuIEVhY2ggdGltZSB0aGUgYWR2ZW50dXJlciB2aXNpdHMgYSByb29tIGNvbnRhaW5pbmcgYSB0cm9sbCwgdGhlIHRyb2xsIHdpbGwgZGVtYW5kIGEgdG9sbCBvZiBhIGNlcnRhaW4gbnVtYmVyIG9mIGdvbGQgcGllY2VzIHdoaWNoIG11c3QgYmUgcGFpZCBiZWZvcmUgY29udGludWluZy48XC9wPlxyXG5cclxuPHA+VGhlIGFkdmVudHVyZXIgYmVnaW5zIHdpdGggMCBHUCBhbmQgdGhlIHByb2JsZW0gaXMgdG8gZGV0ZXJtaW5lIHdoZXRoZXIgdGhlIGFkdmVudHVyZXIgY2FuIG1ha2UgaGVyIHdheSBmcm9tIHJvb20gMSB0byB0aGUgaGlnaGVzdCBudW1iZXJlZCByb29tLiBJZiB0aGUgaGlnaGVzdCBudW1iZXJlZCByb29tIGNvbnRhaW5zIGEgdHJvbGwsIHRoZSBhZHZlbnR1cmVyIG11c3QgYWxzbyBiZSBhYmxlIHRvIHBheSB0aGUgdG9sbCBvbiBhcnJpdmFsLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgd2lsbCBjb25zaXN0IG9mIGEgc2VxdWVuY2Ugb2YgbWF6ZXMuIEVhY2ggbWF6ZSB3aWxsIGJlZ2luIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBzcGVjaWZ5aW5nIHRoZSBudW1iZXIgb2Ygcm9vbXMgaW4gdGhlIG1hemUgKG4sIDEgJmxlOyBuICZsZTsgMTAwMCkuIFRoaXMgd2lsbCBiZSBmb2xsb3dlZCBieSBuIGxpbmVzIHNwZWNpZnlpbmcgdGhlIHJvb21zIGluIGFzY2VuZGluZyBvcmRlci4gRWFjaCBsaW5lIHdpbGwgc3BlY2lmeSB0aGUgY29udGVudHMgb2YgdGhlIHJvb20gKGVtcHR5IChFKSwgYSBsZXByZWNoYXVuIChMKSBvciBhIHRyb2xsIChUKSksIGZvbGxvd2VkIGJ5IGEgbnVtYmVyIHNwZWNpZnlpbmcgdGhlIG51bWJlciBvZiBHUCB0aGF0IHRoZSBsZXByZWNoYXVuIHdpbGwgdG9wIHVwIHRvLCBvciB0aGF0IHRoZSB0cm9sbCB3aWxsIHJlcXVpcmUgZnJvbSB0aGUgYWR2ZW50dXJlci4gKEZvciBlbXB0eSByb29tcyB0aGlzIGFtb3VudCBpcyAwLikgVGhlIHJlc3Qgb2YgdGhlIGxpbmUgY29uc2lzdHMgb2YgYSBsaXN0IG9mIDEgb3IgbW9yZSBudW1iZXJzIGluIHRoZSByYW5nZSAxLi5uIGFuZCB0ZXJtaW5hdGVkIGJ5IGEgemVybyAoMCksIHJlcHJlc2VudGluZyB0aGUgbnVtYmVycyBvbiB0aGUgZG9vcnMgb2YgdGhhdCByb29tLiBUaGUgc2VxdWVuY2Ugb2YgbWF6ZXMgaXMgdGVybWluYXRlZCBieSBhIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSB6ZXJvICgwKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgd2lsbCBjb25zaXN0IG9mIGEgc2VxdWVuY2Ugb2YgbGluZXMsIG9uZSBmb3IgZWFjaCBtYXplICZtZGFzaDsgZWl0aGVyICZsZHF1bztZZXMmcmRxdW87IG9yICZsZHF1bztObyZyZHF1bzsgaW5kaWNhdGluZyB3aGV0aGVyIGl0IGlzIHBvc3NpYmxlIHRvIHJlYWNoIHRoZSBmaW5hbCByb29tIGZyb20gdGhlIGZpcnN0IG9uZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=