You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

样例输入

2

3 0

3 4 5

5 4 3

3 100

-3 -4 -5

30 40 50

样例输出

2

-1

样例解释

第一组数据中，从 2 或者 3 出发都可以走完一圈，2 编号更小，而从 1 出

发，第一条路就走不出去第二组数据不难看出是不可能走一圈的。

数据范围及约定

存在 30% 的数据, n ≤ 2000.

另外存在 30% 的数据, c = 0.

100% 的数据范围在题面中已提到过