p2.cpp

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;

int minLines(const vector<unordered_set<int>> &graph, int num_lines, int starting_line, int ending_line) {

   
    queue<int> q;
    q.push(starting_line);
    int changes = 0;
    vector<int> visited(num_lines, 0);
    visited[starting_line] = 1;

    while (!q.empty()) {
        int size = q.size();      

       
        for (int i = 0; i < size; ++i) {
            int current_line = q.front();
            q.pop();

            if (current_line == ending_line) {
                return changes;   
            }

           
            for (int connected_line : graph[current_line]) {
                if (!visited[connected_line]) {
                    visited[connected_line] = 1;
                    q.push(connected_line);
                }
            }
        }

        
        ++changes;
    }
    return -1;
}



int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int num_stations, num_ligacoes, num_lines;
    cin >> num_stations >> num_ligacoes >> num_lines;
    vector<unordered_set<int>> station_lines(num_stations);
    vector<unordered_set<int>> line_connections(num_lines);
    vector<int> aux(num_ligacoes);  // para keep track se uma linha conecta todas as stations
    for (int i = 0; i < num_ligacoes; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        --x; --y; --z;
        aux[z]++;
        for (int line : station_lines[x]) {
            if (line != z) {
                line_connections[line].insert(z);
                line_connections[z].insert(line);
            }
        }
        
        for (int line : station_lines[y]) {
            if (line != z) {
                line_connections[line].insert(z);
                line_connections[z].insert(line);
            }
        }
        
       
        station_lines[x].insert(z);
        station_lines[y].insert(z);
    }
    if(num_stations == 1 && (num_lines == 1 || num_lines == 0)){
        cout << 0 << endl;
        return 0;
    }
   
    for(int i = 0; i < num_stations; ++i){
        if(station_lines[i].empty()){
            cout << -1 << endl;
            return 0;
        }
    }
    
    for(int i = 0; i < num_lines; ++i){
        if(aux[i]>= num_stations - 1){
            cout << 0 << endl;
            return 0;
        }
    }


    //BFS
    int max = 0;
    for(int i = 0; i < num_lines; ++i){
        for(int j = i+1; j < num_lines; ++j) {
            int min = minLines(line_connections, num_lines, i, j);
            if(min == -1){
                cout << -1 << endl;
                return 0;
            }
            if(min > max){
                max = min;
                if(max >= num_lines - 1){
                    cout << max << endl;
                    return 0;
                }
            }
        }
    }
    cout << max << endl;
    return 0;
}