Training Site
Sideways banner

Myrtle Rust

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 100 megabytes
Time limit: 1.0 seconds

Myrtle Rust, a wind-borne fungus which effects native NZ plants, has made its way into a nursery in the upper North. Every morning, trucks carrying plants (which might be infected) leave their starting nursery and make it to a corresponding destination nursery at the end of the day. If the truck contains an infected plant, all plants in the destination nursery will become infected overnight. This means all the trucks which leave form this nursery the next day will carry infected plants!

Given a description of all nurseries and how plants are moved between them, write a program to calculate how many days it will take for North Island nurseries to become completely infected with Myrtle Rust.

Input

The first line will contain three numbers separated by a single space. The first, N, is the number of North Island nurseries, the second, Z, is the number corresponding to the nursery which became infected first, and the last, T, is the number of trucks in the nursery network. Note that nurseries are numbered from 0 up to N – 1.

What follows are T lines, one for each truck. Each line will contain two space-separated integers. The first, s, is the number corresponding to the nursery in which the truck starts at, and the second, d, is the truck’s destination nursery. Every nursery will be connected to the network via a truck.

Output

  • Print a single number representing how many days it takes for the North Island to become infected with Myrtle Rust.
  • If the North Island never becomes fully infected with Myrtle Rust then print -1

Subtasks

  • 60%: The truck's delivery routes form a single chain of nurseries. E.g. Truck 0 goes from nursery 1 to nursery 2 and truck 1 goes from nursery 2 to nursery 3 to form a continuous open-ended chain.
  • 40%: The full problem.
  • Sample Input 1

    4 0 3
    0 1
    1 2
    2 3
    

    Sample Output 1

    3
    
  • Sample Input 2

    4 1 5
    1 3
    1 2
    0 2
    1 0
    2 0
    

    Sample Output 2

    1
    
  • Sample Input 3

    4 2 3
    0 1
    1 2
    2 3
    

    Sample Output 3

    -1