Проделав долгий путь в поисках древних сокровищ, Оливер готов приступить к финальному испытанию.

Оливер находится в системе подземных комнат, соединённых туннелями. Чтобы избежать ловушек, каждый туннель можно пройти только в одном направлении.

Изначально Оливер находится в комнате $$$1$$$, а сокровище – в комнате $$$n$$$. Однако везде абсолютная темнота, поэтому, чтобы добраться до комнаты $$$n$$$, он будет использовать имеющиеся у него $$$k$$$ переносных ламп. Когда Оливер находится в комнате, он может либо поставить в неё лампу, если у него на руках остаётся хотя бы 1 лампа (если в комнате темно), либо забрать лампу оттуда (если он туда её до этого ставил). Однако перемещаться по туннелю $$$u → v$$$, исходящему из его комнаты $$$u$$$, он может только в том случае, если хотя бы в одной из комнат $$$u, v$$$ находится лампа, которая освещает проход (освещённая комната освещает все проходы, входящие и исходящие из этой комнаты).

Каждая лампа сама по себе является ценным артефактом Оливера, поэтому он хочет пройти путь до комнаты $$$n$$$ и сохранить все лампы при себе, а не разбросанными по лабиринту.

В то же время Оливер может использовать силу ламп, чтобы освещать большие пространства. Изначально у него есть массив $$$c$$$ особых комнат, в котором содержится только комната $$$1$$$ (то есть $$$c = [1]$$$). Если Оливер ставит хоть одну из своих ламп в комнату $$$x$$$, которая находится в массиве $$$c$$$, то все комнаты из массива $$$c$$$ становятся освещёнными.

При этом каждый тринадцатый раз, когда Оливер заходит в одну и ту же комнату $$$u$$$, если из неё есть ребро в комнату, находящуюся в массиве $$$c$$$, то данная комната $$$u$$$ добавляется в массив $$$c$$$.

Помогите Оливеру определить, может ли он добраться до сокровища при заданных условиях.