Limits 1s, 512 MB

You are given a bidirectional graph with N vertices and M edges. All edges are painted into either red or black. Your job is to find a spanning tree with some prime number of red edges.

Input First line contains the number of test cases T(1≤ T ≤10).

For each test case:

First line consists of two integers denoting N(1≤ N ≤100000) and M(0≤ M ≤200000).

Next M lines consist of two integers A, B and C denoting there is a directed road from A to B (1≤ A,B ≤N) with color C(0 for black and 1 for red).The graph may contain self loops and multiple edges between two nodes.

Output For every test case, you need to print “Case T: ” (where T is the test case number) followed by the prime number. If you can not construct such a tree print -1. If you can use multiple prime, print the largest one.

Sample Input Output 3 3 3

1 2 0

2 3 1

1 3 1

5 6

1 2 1

2 3 0

3 4 1

1 5 1

5 4 0

2 4 1

5 4

1 2 1

1 3 1

1 4 1

1 5 1 Case 1: 2

Case 2: 3

Case 3: -1

Test Case 1: You can make a spanning tree by connecting

edge 1-2, 2-3 with 1 red edge edge 1-2, 1-3 with 1 red edge edge 1-2, 2-3 with 2 red edges as 2 is the largest prime that can be used to construct a spanning tree, the answer is 1. Test Case 2: You can make a spanning tree in several ways. I'll describe three of them below.

connect edge 1-2, 2-4, 4-5 ,4-3 with 3 red edges connect edge 1-5, 5-4, 4-2, 2-3 with 2 red edges connect edge 1-5, 1-2, 2-4, 4-3 with 4 red edges as 4 is not a prime and 3 is larger between 2 and 3, the answer is 3. Test Case 3: The only way you can make a spanning tree is using 4 red edges. But 4 is not a prime. Hence the answer is -1.