The police is already looking for him and has sent $K$ patrols, indexed from $0$ to $K-1$ to guard the manholes connected to the sewer system.
There are $N$ manholes, indexed from $0$ to $N-1$ and $M$ tunnels connecting pairs of them. Valerio's friend Filippo is waiting for him nearby manhole $N-1$, if he can reach it, he will escape safely.

Valerio starts from manhole $0$ and, every minute, he can choose to move to a manhole adjacent to the one he is in or to stay another minute under the same manhole.
Each police patrol guard $L_i$ manholes, indexed from $0$ to $L_i-1$. Patrol $i$ is initially guarding manhole $H_{i,0}$, every minute it moves from manhole $H_{i,j}$ to manhole $H_{i,j+1}$, after reaching manhole $H_{i,L_i-1}$, it return to manhole $H_{i,0}$.
 

h2. Date de intrare
Fişierul de intrare $patrol2.in$ ...