Task Scheduling

You are given a total of n tasks and m dependency pairs. Each dependency pair [a, b] means that task a must be completed before task b can start. Your goal is to determine whether it is possible to finish all tasks without running into a circular dependency.

This problem can be modeled as detecting a cycle in a directed graph. By using topological sorting (Kahn's algorithm), you can decide if the tasks can be completed: if the graph has no cycle, then a valid order exists and the answer is \(\texttt{true}\); otherwise, it is \(\texttt{false}\).

inputFormat

The input is read from standard input (stdin). The first line contains two space-separated integers n and m, where n is the number of tasks (numbered from 0 to n-1) and m is the number of dependencies. Each of the next m lines contains two integers a and b indicating that task a must be completed before task b can start.

outputFormat

Output to standard output (stdout) a single string: "true" if it is possible to finish all tasks; otherwise, "false".## sample

2 1
1 0

true