CEO Message Propagation

In a company with N employees, messages are passed along directed communication links. The CEO (employee 1) initiates the message. Each directed connection (u, v) means that employee u can send the message to employee v. Your task is to determine if the message initiated by the CEO can eventually reach all N employees. If all employees receive the message (directly or indirectly), print 1; otherwise, print -1.

The problem can be formulated as checking whether all nodes in a directed graph are reachable from node 1. Formally, given a directed graph (G=(V,E)) with (|V| = N) and (|E| = M), determine if the set (R) of nodes reachable from node 1 is equal to (V).

Input Format (see below)

Output Format (see below)

Example:

For (N=5), (M=4) and the connections:

1 2 2 3 3 4 4 5

The output should be 1 because all employees are reachable from the CEO.

inputFormat

The first line contains two integers (N) (the number of employees) and (M) (the number of connections). Each of the next M lines contains two integers (u) and (v) indicating a directed connection from employee (u) to employee (v).

outputFormat

Output a single integer: 1 if all employees can be reached starting from employee 1 (the CEO) via the given connections, and -1 otherwise.## sample

5 4
1 2
2 3
3 4
4 5

1