Untitled

3

15 16

0 2

1 2

2 3

3 4

3 5

4 6

5 7

6 8

7 8

7 9

8 10

9 11

10 12

11 12

10 13

12 14

3 2

0 1

1 2

15 16

0 2

1 2

2 3

3 4

3 5

4 6

5 7

6 8

7 8

7 9

8 10

9 11

10 12

11 12

10 13

12 14
package Buoi28.The_Settlers_of_Catan;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {

	static int nNodes;
	static int nEdges;

	static int[][] list;
	static int[] info;

	static int[][] matrix;

	static int max;

	public static void input(Scanner sc) {
		nNodes = sc.nextInt();
		nEdges = sc.nextInt();
		list = new int[nNodes][3];
		info = new int[nNodes];
		matrix = new int[nNodes][nNodes];

		max = Integer.MIN_VALUE;
		for (int i = 0; i < nEdges; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			matrix[a][b] = 1;
			matrix[b][a] = 1;

			list[a][info[a]] = b;
			list[b][info[b]] = a;
			info[a]++;
			info[b]++;
		}
	}

	public static void backtrack(int k, int count) {
		for (int i = 0; i < info[k]; i++) {
			int a = list[k][i];
			if (matrix[k][a] == 1) {
				matrix[k][a] = 0;
				matrix[a][k] = 0;
				backtrack(a, count + 1);
				matrix[k][a] = 1;
				matrix[a][k] = 1;
			}
		}
		if (max < count) {
			max = count;
		}
	}

	public static void solve() {
		for (int i = 0; i < nNodes; i++) {
			backtrack(i, 0);
		}
		System.out.println(max);
	}

	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
		long start = System.currentTimeMillis();
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int T;
		T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			input(sc);
			solve();
		}
		long end = System.currentTimeMillis();
		System.out.println((double) (end - start) / 1000);
	}

}