Today, Ciel's restaurant is closed. Ciel is bored, so she decides to take a walk randomly.

This town has N intersections and M one way roads. The i-th road connects from the A_i-th intersection to the B_i-th intersection. Ciel is in the 1st intersection now, and Ciel's house is in the N-th intersection.

If Ciel is in the i-th intersection, she will take a walk as follows: