Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.2 kB
1
Indexable
Never
import java.util.Scanner;


public class TheSettlersOfCatan {
	static int n, m, cMax;
	static final int MAX = 100;
	static int[] edgeS = new int[MAX];
	static int[] edgeE = new int[MAX];
	
	static void backtracking(int idx, int count){
		if (count > cMax){
			cMax = count;
		}
		for(int i = 0; i < m; i++){
			if(edgeS[i] == idx){
				int t1, t2;
				t1 = edgeS[i];
				t2 = edgeE[i];
				edgeS[i] = -1;
				edgeE[i] = -1;
				backtracking(t2,  count + 1);
				edgeS[i] = t1;
				edgeE[i] = t2;
			}else if(edgeE[i] == idx){
				int t1, t2;
				t1 = edgeS[i];
				t2 = edgeE[i];
				edgeS[i] = -1;
				edgeE[i] = -1;
				backtracking(t1, count + 1);
				edgeE[i] = t1;
				edgeS[i] = t2;
			}
		}
	}
	
	public static void main(String agr[]){
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for(int test_case = 1; test_case <= t; test_case++){
			cMax = 0; 
			n = sc.nextInt();
			m = sc.nextInt();
			for(int i = 0; i < m; i++){
				edgeS[i] = sc.nextInt();
				edgeE[i] = sc.nextInt();
			}
			for(int i = 0; i < n; i++){
				backtracking(i, 0);
			}
			
			
			System.out.println(cMax);
			
		}
	}
}