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.
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.
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.
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
Test Case 2:
You can make a spanning tree in several ways. I'll describe three of them below.
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.