SP70 RELATS1 - Relations

You are given a directed graph, whose edges are labeled with relational symbols '' and '='. For a nonnegative integer k, a k-correct G-labeling is a mapping from vertices of G into integers from interval \[0,k\] such that numbers at the ends of each edge satisfy the relation described by the label of the edge. We assume that an element on the left side of the relational symbol is a number assigned to the initial vertex. Compute the smallest k for which k-correct G-labeling exists or verify that such labeling doesn't exist for any k.

The first line of the input file contains one positive integer d not larger than 10. This is the number of data sets. The data sets follow. Each data set is described in two consecutive lines of the input file. In the first line there are two integers n and m separated by a single space. The number n is the number of vertices of G and m is the number of edges of G. Numbers n and m satisfy the inequalities: 1

For the i-th data set, 1