Untitled

#include<iostream>
using namespace std;

int nt; // Số lượng bộ test
int n, m; // Số đỉnh và số cạnh trong đồ thị
int map[21][21]; // Ma trận lưu trữ đồ thị
int dem[21]; // Mảng đếm số lần đi qua mỗi đỉnh
int vx, vy; // Biến tạm thời lưu giá trị các đỉnh trong cạnh

// Khởi tạo lại ma trận đồ thị
void restmap() {
    for(int i = 0; i <= n; i ++) {
        for(int j = 0; j <= n; j++) {
            map[i][j]= 0;
        }
    }
}

// Khởi tạo lại mảng đếm số lần đi qua đỉnh
void resetDem() {
    for(int i  =0 ; i <= n; i++) {
        dem[i]=0;
    }
}

// Đếm số lượng đỉnh khác nhau đã đi qua
int countdiem() {
    int len = 0;
    for(int i = 1; i <= n; i++) {
        if(dem[i]!=0) {
            len++;
        }
    }
    return len;
}

// Thuật toán Backtracking để tìm đường đi tối ưu
void Backtrack(int v) {
    // Nếu đến được đích và số đỉnh 1 và 2 đều được đi qua đúng số lần
    if(v==1 && dem[1]==2 && dem[2]==1) {
        // Đếm số lượng đỉnh khác nhau đã đi qua và cập nhật vào mindiem
        int len = countdiem();
        if(len < mindiem) {
            mindiem = len;
        }
        return;
    }
    // Nếu số đỉnh khác nhau đã đi qua lớn hơn mindiem, dừng lại
    if(countdiem() > mindiem) {
        return;
    }

    // Thử tất cả các cách di chuyển từ đỉnh hiện tại v
    for(int i = 1; i <= n; i++) {
        // Nếu có đường đi từ v đến i và số lần đi qua đỉnh i chưa đạt tối đa
        if(map[v][i] == 1 && ((dem[2]==1 && dem[i] < 2) || (dem[2]==0 && dem[i]<1))) {
            // Đánh dấu đã đi qua đỉnh i
            dem[i]++;
            // Thử di chuyển đến đỉnh i
            Backtrack(i);
            // Quay lui: bỏ đánh dấu đã đi qua đỉnh i
            dem[i]--;
        }
    }
}

int main() {
    // Đọc số lượng bộ test
    cin >> nt;
    for(int test = 1; test <= nt; test++) {
        // Đọc số đỉnh và số cạnh của đồ thị
        cin >> n >> m;
        // Khởi tạo lại ma trận đồ thị và mảng đếm số lần đi qua đỉnh
        restmap();
        resetDem();
        // Đọc các cạnh của đồ thị và lưu vào ma trận đồ thị
        for(int i = 0; i < m; i++) {
            cin >> vx >> vy;
            map[vx][vy] = 1;
        }

        // Khởi tạo biến mindiem với giá trị lớn để lưu số đỉnh tối thiểu cần đi qua
        mindiem = 9999999;
        // Bắt đầu thử tất cả các đường đi có thể từ đỉnh 1
        dem[1] = 1;
        Backtrack(1);
        // In ra màn hình số đỉnh tối thiểu cần đi qua từ đỉnh 1 đến đỉnh 2 và quay lại đỉnh 1
        cout << mindiem << endl;
    }
    return 0;
}