After a long journey in search of ancient treasures, Oliver is ready to begin the final trial.

Oliver is in a system of underground rooms connected by tunnels. To avoid traps, each tunnel can be traversed in only one direction.

Initially, Oliver is in room $$$1$$$, and the treasure is in room $$$n$$$. However, it is completely dark everywhere, so to reach room $$$n$$$, he will use the $$$k$$$ portable lamps he has. When Oliver is in a room, he may either place a lamp there, if he still has at least 1 lamp with him (and the room is dark), or pick up a lamp from there (if he had previously placed it there). However, he may move through a tunnel $$$u \to v$$$, leaving his current room $$$u$$$, only if at least one of the rooms $$$u, v$$$ contains a lamp that illuminates the passage (an illuminated room illuminates all passages entering and leaving that room).

Each lamp is itself a valuable artifact for Oliver, so he wants to reach room $$$n$$$ and keep all lamps with him, rather than leaving them scattered throughout the labyrinth.

At the same time, Oliver can use the power of the lamps to illuminate larger areas. Initially, he has an array $$$c$$$ of special rooms, which contains only room $$$1$$$ (that is, $$$c = [1]$$$). If Oliver places at least one of his lamps in a room $$$x$$$ that belongs to the array $$$c$$$, then all rooms from the array $$$c$$$ become illuminated.

Moreover, every thirteenth time Oliver enters the same room $$$u$$$, if there is an edge from it to a room belonging to the array $$$c$$$, then this room $$$u$$$ is added to the array $$$c$$$.

Help Oliver determine whether he can reach the treasure under the given conditions.