// Problema 3, TEMA 1, a) : "https://leetcode.com/problems/course-schedule-ii/" ______________________________________________________________________________________________________
//#include <iostream>
//#include <vector>
//#include <algorithm>
//
//using namespace std;
//
//class Solution {
//public:
//    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
//        int &v = numCourses; //alisul numarului de cursuri
//
//        vector<int> adj[v];
//
//        for(auto &ans : prerequisites){ // Folosim & deoarece vrem sa extragem din prerequisites fiecare pereche de vectori, deci avem nevoie de adresele lor
//            adj[ans[1]].emplace_back(ans[0]); // Adugam nodurile in matricea de adiacenta
//        }
//
//        vector<bool> viz(v, false), pathviz(v, false);
//        vector<int> rezultat;
//
//        for(int node = 0; node < v; node++){
//            if(viz[node] == false && dfs(adj, viz, pathviz, rezultat, node)){ // Daca nu am vizitat deja nodul putem apela dfs, daca este dfs == true inseamna ca avem ciclu deci returnam nimic adica : {}
//                return{};
//            }
//        }
//
//        reverse(rezultat.begin(), rezultat.end());
//        return rezultat;
//
//    }
//
//private:
//    bool dfs(vector<int> adj[], vector<bool>& viz, vector<bool>& pathviz, vector<int>& rezultat, int node){
//
//        if(pathviz[node]) // Verificam daca in parcurgerea nodului curent avem sau nu ciclu. Daca avem returnam true deoarece ne intoarce in recursivitatea dfs-ului si o sa se tot returneze true pana la final
//            return true;
//
//        if(viz[node]) // Verificam daca nodul a mai fost vizitat in alte parcurgeri, daca a fost vizitat nu mai are sens sa verificam nimic.
//            return false;
//
//        viz[node] = pathviz[node] = true; // Le facem true ca sa stim ca le-am vizitat.
//
//        for(auto nd : adj[node]){  // In acest for luam fiecare vecin al nodului curent si apelam dfs pentru ei, daca dfs-ul returneaza true inseamna ca avem bucla si nu e bine
//            if(dfs(adj, viz, pathviz, rezultat, nd)){
//                return true;
//            }
//        }
//
//        pathviz[node] = false; // Nu mai avem acum nevoie de pathviz deci il facem false ca sa il avem cand apelam urmatorul nod.
//        rezultat.emplace_back(node);
//        return false;
//    }
//};
//
//int main() {
//    Solution solution;
//
//    int numCourses = 4;
//    vector<vector<int>> prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
//
//    vector<int> result = solution.findOrder(numCourses, prerequisites);
//
//    if (result.empty()) {
//        cout << "Nu se poate forma un program valid!" << endl;
//    } else {
//        cout << "Ordinea cursurilor este: ";
//        for (int course : result) {
//            cout << course << " ";
//        }
//        cout << endl;
//    }
//
//    return 0;
//}
// Problema 3, TEMA 1, b) : "https://leetcode.com/problems/course-schedule-ii/" _____________________________________________________________________________________________________________________________
//#include <iostream>
//#include <vector>
//#include <algorithm>
//
//using namespace std;
//
//class Solution {
//public:
//    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
//        int &v = numCourses; //alisul numarului de cursuri
//
//        vector<int> adj[v];
//
//        for(auto &ans : prerequisites){ // Folosim & deoarece vrem sa extragem din prerequisites fiecare pereche de vectori, deci avem nevoie de adresele lor
//            adj[ans[1]].emplace_back(ans[0]); // Adugam nodurile in matricea de adiacenta
//        }
//
//        vector<bool> viz(v, false), pathviz(v, false);
//        vector<int> rezultat;
//
//        for(int node = 0; node < v; node++){
//            if(!viz[node]){
//                vector<int> ciclu = dfs(adj, viz, pathviz, rezultat, node);
//                if(!ciclu.empty()){
//                    ciclu.emplace_back(ciclu[0]);
//                    return ciclu;
//                }
//            }
//        }
//
//        reverse(rezultat.begin(), rezultat.end());
//        return rezultat;
//
//    }
//
//private:
//    vector<int> dfs(vector<int> adj[], vector<bool>& viz, vector<bool>& pathviz, vector<int>& rezultat, int node){
//
//        if(pathviz[node]) // Verificam daca in parcurgerea nodului curent avem sau nu ciclu. Daca avem returnam true deoarece ne intoarce in recursivitatea dfs-ului si o sa se tot returneze true pana la final
//            return {node}; // in cazul punctului b) returnam nodul respectiv
//
//        if(viz[node]) // Verificam daca nodul a mai fost vizitat in alte parcurgeri, daca a fost vizitat nu mai are sens sa verificam nimic.
//            return {}; // in cazul punctului b) returnam nimic
//
//        viz[node] = pathviz[node] = true; // Le facem true ca sa stim ca le-am vizitat.
//
//        for(auto nd : adj[node]){  // In acest for luam fiecare vecin al nodului curent si apelam dfs pentru ei, daca dfs-ul returneaza true inseamna ca avem bucla si nu e bine
//            vector<int> ciclu = dfs(adj, viz, pathviz, rezultat, nd);
//            if(!ciclu.empty()){
//                return ciclu; //adica returnam tot ciclul
//            }
//        }
//
//        pathviz[node] = false; // Nu mai avem acum nevoie de pathviz deci il facem false ca sa il avem cand apelam urmatorul nod.
//        rezultat.emplace_back(node);
//        return {};
//    }
//};
//
//int main() {
//    Solution solution;
//
//    int numCourses = 4;
//    vector<vector<int>> prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
//
//    vector<int> result = solution.findOrder(numCourses, prerequisites);
//
//    if (result.empty()) {
//        cout << "Nu se poate urma nicio ordine de cursuri." << endl;
//    } else {
//        cout << "Ordinea cursurilor: ";
//        for (int course : result) {
//            cout << course << " ";
//        }
//        cout << endl;
//    }
//
//    return 0;
//}

// Problema 4, TEMA 1: "https://www.infoarena.ro/problema/ctc"____________________________________________________________________________________________________________

//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//
//const int NEVIZITAT = -1;
//int n, m, ids[100001], low[100001], id = 0, sccCount = 0;
//vector<int> g[100001];
//stack<int> stiva;
//vector<bool> onStack(100001, false);
//
//void DFS(int node){
//
//    stiva.push(node);
//    onStack[node] = true;
//    ids[node] = low[node] = id++;
//
//    for(auto from : g[node]){
//        if(ids[from] == NEVIZITAT){
//            DFS(from);
//        }
//
//        if(onStack[from]){
//            low[node] = min(low[from], low[node]);
//        }
//    }
//
//    if(low[node] == ids[node]){
//        while (!stiva.empty()) {
//            int nod = stiva.top();
//            stiva.pop();
//
//            onStack[nod] = false;
//            low[nod] = ids[node];
//
//            if (nod == node) {
//                break;
//            }
//        }
//        sccCount++;
//    }
//
//
//}
//
//int main() {
//
//    fin >> n >> m;
//    for(int i = 1; i <= m; i++){
//        int x, y;
//        fin >> x >> y;
//        g[x].push_back(y);
//    }
//    for(int i = 1; i <= n; i++){
//        ids[i] = NEVIZITAT;
//    }
//
//    for(int i = 1; i <= n; i++){
//        if(ids[i] == NEVIZITAT){
//            DFS(i);
//        }
//    }
//    cout << sccCount;
//    return 0;
//}

// Problema 5, TEMA 1____________________________________________________________________________________________________________

//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//
//const int NEVIZITAT = -1;
//int n, m, ids[100001], low[100001], id = 0, sccCount = 0;
//vector<int> g[100001];
//stack<int> stiva;
//vector<bool> onStack(100001, false);
//int viz[101], viz1[101];
//int dis_p1[101], dis_p2[101], p, u, q1[101], q2[101];
//
//void BFS1(int node){
//    p = u = 1;
//    viz[node]++;
//    q1[p] = node;
//    while(p <= u){
//        int ans = q1[p];
//        p++;
//        for(auto urm : g[ans]){
//            if(viz[urm] == 0){
//                viz[urm]++;
//                u++;
//                q1[u] = urm;
//                dis_p1[urm] = dis_p1[ans] + 1;
//            }
//        }
//    }
//}
//
//void BFS2(int node){
//    p = u = 1;
//    viz1[node]++;
//    q2[p] = node;
//    while(p <= u){
//        int ans = q2[p];
//        p++;
//        for(auto urm : g[ans]){
//            if(viz1[urm] == 0){
//                viz1[urm]++;
//                u++;
//                q2[u] = urm;
//                dis_p2[urm] = dis_p2[ans] + 1;
//
//            }
//        }
//    }
//}
//
//int main() {
//
//    fin >> n >> m;
//    for(int i = 1; i <= m; i++){
//        int x, y;
//        fin >> x >> y;
//        g[x].push_back(y);
//        g[y].push_back(x);
//    }
//    int p1, p2;
//    fin >> p1 >> p2;
//    BFS1(p1);
//    BFS2(p2);
//
//
//    for(int i = 1; i <= n; i++){
//        int ans = min(dis_p1[i], dis_p2[i]);
//        cout << ans << ' ';
//    }
//
//    return 0;
//}

// Problema 6 SUPLIMENTARA, TEMA 1____________________________________________________________________________________________________________


//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//
//class Solution {
//public:
//    void dfs(int i, int p, vector<int>& v, int ids[], int low[], int &id, vector<int> adj[], vector<vector<int>>& ans){
//        v[i] = 1;
//        ids[i] = low[i] = id++;
//        for(auto vecin: adj[i]){ // Parcurg toti vecinii nodului meu
//            if(vecin == p){ // Verific daca este egal cu parintele nodului ca sa nu ma intorc
//                continue;
//            }
//            if(v[vecin]){ // Daca este deja vizitat inseamna ca am ciclu deci inseamna ca trebuie sa ii incadrez in acelasi ciclu.
//                low[i] = min(low[i], ids[vecin]);
//            }
//            else{
//                dfs(vecin, i, v, ids, low, id, adj, ans); // fac dfs
//                low[i] = min(low[i], low[vecin]); // cand ma intorc dintr-un nod, indiferent din ce nod ma intorc, fac acest lucru ca sa ii incadrez in ac ciclu. Daca low[vecin]
//                if(low[vecin] > ids[i]){ // este mai mare asta inseamna ca(eu deja am fct dfs la vecin) nu a gasit alta ruta spre ciclu meu deci e muchie critica)
//                    ans.push_back({i, vecin});
//                }
//            }
//        }
//    }
//
//    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
//        vector<int>adj[n];
//        for(int i = 0; i < connections.size(); i++){
//            adj[connections[i][0]].push_back(connections[i][1]);
//            adj[connections[i][1]].push_back(connections[i][0]);
//        }
//        int id = 1;
//        vector<int>v(n, 0);
//        int ids[n], low[n];
//        vector<vector<int>>ans;
//        dfs(0, -1, v, ids, low, id, adj, ans);
//        return ans;
//    }
//};
//
//
//int main() {
//
//
//
//    return 0;
//}

// Problema 7 SUPLIMENTARA, TEMA 1____________________________________________________________________________________________________________


//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin ("graf.in");
//ofstream fout ("graf.out");
//
//const int NMAX = 1005;
//const int inf = 2e9;
//const int di[] = {0, 0, 1, -1};
//const int dj[] = {1, -1, 0, 0};
//
//int G[NMAX][NMAX];
//int dp[NMAX][NMAX];
//
//int n, m, ps, cs, pf, cf;
//
//void borderMatrix()
//{
//    for(int i = 1; i <= n; i ++)
//        G[i][0] = G[i][m + 1] = -1;
//    for(int j = 1; j <= m; j ++)
//        G[0][j] = G[n + 1][j] = -1;
//}
//
//bool ok(int x, int y){
//    return x >= 1 && x <= n && y >= 1 && y <= m;
//}
//
//
//
//void lee(){
//    deque<pair<int, int>> q;
//    q.push_front(make_pair(ps, cs));
//    dp[ps][cs] = 1;
//    while (!q.empty()){
//        int x = q.front().first;
//        int y = q.front().second;
//        q.pop_front();
//        for(int i = 0; i < 4; i++){
//            int xn = x + di[i];
//            int yn = y + dj[i];
//            if(dp[xn][yn] > dp[x][y] + (G[x][y] != G[xn][yn])){
//                if(G[x][y] == G[xn][yn]){
//                    if(dp[xn][yn] > dp[x][y]){
//                        dp[xn][yn] = dp[x][y];
//                    }
//                    q.push_front(make_pair(xn, yn));
//                }
//                else{
//                    dp[xn][yn] = dp[x][y] + 1;
//                    q.push_front(make_pair(xn, yn));
//                }
//            }
//        }
//    }
//}
//
//
//
//int main(){
//    fin >> n >> m >> ps >> cs >> pf >> cf;
//    borderMatrix();
//    for(int i = 1; i <= n; i++){
//        for(int j = 1; j <= m; j++){
//            fin >> G[i][j];
//        }
//    }
//    for(int i = 1; i <= n; i++){
//        for(int j = 1; j <= m; j++){
//            dp[i][j] = inf;
//        }
//    }
//    lee();
//    fout<<dp[pf][cf] - 1<<"\n";
//}

// Problema 8 SUPLIMENTARA, TEMA 1____________________________________________________________________________________________________________


//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//
//int n, m, x, y, viz[7501], d1[7501], d2[7501], frecventa[7501], ans[7501];
//vector<int> adj[7501];
//
//void BFS(int node, int d[]){
//    for(int i = 1; i <= n; i++){
//        viz[i]=0;
//    }
//    queue<int> q;
//    q.push(node);
//    viz[node] = 1;
//    while(!q.empty()){
//        int aux = q.front();
//        q.pop();
//        for(int i = 0; i < adj[aux].size(); i++){
//            if(viz[adj[aux][i]] == 0){
//                q.push(adj[aux][i]);
//                viz[adj[aux][i]] = 1;
//                d[adj[aux][i]] = d[aux] + 1;
//            }
//        }
//    }
//}
//
//int main(){
//
//    fin >> n >> m >> x >> y;
//    for(int i = 1; i <= m; i++){
//        int a, b;
//        fin >> a >> b;
//        adj[a].push_back(b);
//        adj[b].push_back(a);
//    }
//
//    BFS(x, d1);
//    BFS(y, d2);
//
//    for(int i = 1; i <= n; i++){
//        if(d1[i] + d2[i] == d1[y]){
//            frecventa[d1[i]]++;
//        }
//    }
//    int ok = 0;
//    for(int i = 1; i <= n; i++){
//        if(d1[i] + d2[i] == d1[y] and frecventa[d1[i]] == 1){
//            ans[++ok] = i;
//        }
//    }
//    fout << ok << endl;
//    for(int i = 1; i <= ok; i++){
//        fout << ans[i] << ' ';
//    }
//    return 0;
//}

// Problema 9 SUPLIMENTARA, TEMA 1 : "https://www.infoarena.ro/problema/lesbulan"____________________________________________________________________________________________________________

//
//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//
//const int maxN = 55;
//int n, m;
//vector <int> G[maxN];
//bool used[maxN], prost, scos[maxN], mat[maxN][maxN];
//
//void dfs(int nod, int tata)
//{
//    used[nod] = 1;
//    int nr = (tata != 0);
//    for(int vecin : G[nod])
//    {
//        if(vecin == tata || scos[vecin])
//            continue;
//        nr++;
//        dfs(vecin, nod);
//    }
//    if(nr == 1)
//        scos[nod] = 1;
//}
//
//void dfs_ciclu(int nod, int tata)
//{
//    if(used[nod])
//    {
//        prost = 1;
//        return;
//    }
//    used[nod] = 1;
//    for(int vecin : G[nod])
//    {
//        if(vecin == tata)
//            continue;
//        dfs_ciclu(vecin, nod);
//    }
//}
//
//void solve()
//{
//    fin >> n >> m;
//    for(int i = 1; i <= m; i++)
//    {
//        int x, y;
//        fin >> x >> y;
//        if(mat[x][y])
//            continue;
//        mat[x][y] = 1;
//        mat[y][x] = 1;
//        G[x].push_back(y);
//        G[y].push_back(x);
//    }
//    prost = 0;
//    for(int i = 1; i <= n; i++)
//        if(!used[i])
//            dfs_ciclu(i, 0); /// daca e ciclu
//    if(prost)
//        fout << "0\n";
//    else
//    {
//        for(int i = 1; i <= n; i++)
//            used[i] = 0;
//        for(int i = 1; i <= n; i++)
//            if(!used[i])
//                dfs(i, 0);
//        for(int i = 1; i <= n; i++)
//            used[i] = 0;
//        for(int i = 1; i <= n; i++)
//            if(!used[i] && !scos[i])
//                dfs(i, 0);
//        for(int i = 1; i <= n; i++)
//        {
//            int grad = 0;
//            for(int vecin : G[i])
//                if(!scos[vecin])
//                    grad++;
//            if(grad > 2)
//                prost = 1;
//        }
//        fout << !prost << '\n';
//    }
//    for(int i = 1; i <= n; i++)
//    {
//        used[i] = 0;
//        scos[i] = 0;
//        G[i].clear();
//        for(int j = 1; j <= n; j++)
//            mat[i][j] = 0;
//    }
//}
//
//int main()
//{
//    int nr_teste;
//    fin >> nr_teste;
//    while(nr_teste--)
//        solve();
//    return 0;
//}

// Problema 10 SUPLIMENTARA, TEMA 1 : "https://leetcode.com/problems/max-area-of-island/"____________________________________________________________________________________________________________


//#include <iostream>
//#include <vector>
//#include <fstream>
//#include <queue>
//
//using namespace std;
//
//class Solution {
//public:
//    int maxAreaOfIsland(vector<vector<int>>& grid) {
//        int result = 0, n = grid.size(), m = grid[0].size();
//
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < m; j++) {
//                if (grid[i][j] == 1)
//                    result = max(result, bfs(grid, i, j, n, m));
//            }
//        }
//
//        return result;
//    }
//
//private:
//    int bfs(vector<vector<int>>& grid, int r, int c, int& n, int& m) {
//        int result = 0;
//
//        queue<pair<int,int>> Q;
//        grid[r][c] = -1; // mark as visited
//        Q.emplace(r, c);
//
//        while (!Q.empty()) {
//            auto [r, c] = Q.front(); Q.pop();
//            result++;
//
//            int DIR[][2] = { {0, -1}, {1, 0}, {0, 1}, {-1, 0} }; // left, up, right, down
//
//            for (int i = 0; i < 4; i++) {
//                int nr = r + DIR[i][0], nc = c + DIR[i][1];
//                if (nr < 0 || nc < 0 || nr >= n || nc >= m || grid[nr][nc] != 1)
//                    continue;
//                grid[nr][nc] = -1; // mark as visited
//                Q.emplace(nr, nc);
//            }
//        }
//
//        return result;
//    }
//};
//
//int main() {
//    ifstream fin("graf.in");
//
//    int n, m;
//    fin >> n >> m;
//
//    vector<vector<int>> grid(n, vector<int>(m));
//
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < m; j++) {
//            fin >> grid[i][j];
//        }
//    }
//
//    Solution solution;
//    int maxIslandArea = solution.maxAreaOfIsland(grid);
//    cout << "Max Island Area: " << maxIslandArea << endl;
//
//    return 0;
//}
// Problema -4 , TEMA 2 : "https://www.infoarena.ro/problema/apm"____________________________________________________________________________________________________________

//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin ("graf.in");
//ofstream fout("graf.out");
//
//const int MAX = 400001;
//
//int n, m, tata[MAX], grad[MAX], ok, sum;
//pair<int, int> ans[MAX];
//
//struct muchie{
//    int x, y, cost;
//}v[MAX];
//
//bool compara(muchie a, muchie b){
//    return a.cost < b.cost;
//}
//
//int cauta(int node){
//    while(tata[node] != node){
//        node = tata[node];
//    }
//    return node;
//}
//
//void uneste(int x, int y){
//    if(grad[x] < grad[y]){
//        tata[x] = y;
//    }
//    if(grad[x] > grad[y]){
//        tata[y] = x;
//    }
//    if(grad[x] == grad[y]){
//        tata[x] = y;
//        grad[y]++;
//    }
//
//}
//
//int main()
//{
//    fin >> n >> m;
//    for(int i = 1; i <= m; i++){
//        fin >> v[i].x >> v[i].y >> v[i].cost;
//    }
//    sort(v + 1, v + m + 1, compara);
//
//    for(int i = 1; i <= n; i++){
//        tata[i] = i;
//        grad[i] = 1;
//    }
//
//    for(int i = 1; i <= m; i++){
//        int aux1 = cauta(v[i].x);
//        int aux2 = cauta(v[i].y);
//        if(aux1 != aux2){
//            uneste(aux1, aux2);
//
//            sum = sum + v[i].cost;
//            ans[++ok].first = v[i].x;
//            ans[ok].second = v[i].y;
//        }
//    }
//    fout << sum << endl;
//    fout << n - 1 << endl;
//    for(int i = 1; i <= ok; i++){
//        fout << ans[i].first << ' ' << ans[i].second << endl;
//    }
//    return 0;
//}



// Problema -1 , TEMA 2 : "https://www.infoarena.ro/problema/apm"____________________________________________________________________________________________________________


//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//
//const int MAX = 400001;
//int n, m, viz[MAX], dist[MAX], inf = 1e9 + 1, tata[MAX];
//vector<pair<int, int>> adj[MAX];
//priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; // Coada de prioritate
//
//void prim(int startNode) {
//    dist[startNode] = 0;
//    q.push({0, startNode});
//
//    while (!q.empty()) {
//        int current = q.top().second;
//        int currentDist = q.top().first;
//        q.pop();
//
//        if (viz[current]) continue;
//
//        viz[current] = 1;
//
//        for (auto neighbor : adj[current]) {
//            int neighborNode = neighbor.first;
//            int neighborDist = neighbor.second;
//
//            if (!viz[neighborNode] && neighborDist < dist[neighborNode]) {
//                dist[neighborNode] = neighborDist;
//                tata[neighborNode] = current;
//                q.push({dist[neighborNode], neighborNode});
//            }
//        }
//    }
//
//    int suma = 0;
//    for (int i = 1; i <= n; i++) {
//        suma += dist[i];
//    }
//
//}
//
//int main() {
//    fin >> n >> m;
//    for (int i = 1; i <= m; i++) {
//        int x, y, cost;
//        fin >> x >> y >> cost;
//        adj[x].push_back({y, cost});
//        adj[y].push_back({x, cost});
//    }
//    for (int i = 1; i <= n; i++) {
//        dist[i] = inf;
//    }
//    prim(1);
//
//    int primCost = 0; // Salvăm costul primului arbore minim
//    for (int i = 2; i <= n; i++) {
//        primCost += dist[i];
//    }
//
//    // Resetați variabilele pentru a calcula al doilea arbore minim
//    for (int i = 1; i <= n; i++) {
//        dist[i] = inf;
//        viz[i] = 0;
//        tata[i] = 0;
//    }
//
//    int secondMinCost = inf; // Inițializăm costul al doilea arbore cu o valoare mare
//    for (int startNode = 1; startNode <= n; startNode++) {
//        if (startNode == 1) continue; // Sărim nodul de start folosit în primul arbore
//        prim(startNode);
//
//        int currentCost = 0; // Costul arborelui generat pentru nodul de start curent
//        for (int i = 2; i <= n; i++) {
//            currentCost += dist[i];
//        }
//
//        // Verificăm dacă costul arborelui este mai mic și diferit de primul arbore
//        if (currentCost != primCost) {
//            secondMinCost = currentCost;
//        }
//    }
//
//    fout << primCost << "\n"; // Afișăm costul primului arbore minim
//    fout << secondMinCost << "\n"; // Afișăm costul celui de-al doilea arbore minim
//
//    return 0;
//}

// Problema 1 , TEMA 2 : "https://www.infoarena.ro/problema/retea2"____________________________________________________________________________________________________________


//#include <bits/stdc++.h>
//#include <iomanip>
//using namespace std;
//
//ifstream fin ("graf.in");
//ofstream fout ("graf.out");
//
//const int NMAX=2e3+5;
//const int INF=2e9;
//
//double dist[NMAX];
//
//struct coords{
//    double x;
//    double y;
//}centrale[NMAX],v[NMAX];
//
//double euclid(coords a,coords b)
//{
//    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
//}
//
//int main()
//{
//    int n, m;
//    fin >> n >> m;
//    for(int i = 1 ; i <= n; i++){
//        fin >> centrale[i].x >> centrale[i].y;
//    }
//    for(int i = 1; i <= m; i++){
//        fin >> v[i].x >> v[i].y;
//        dist[i] = euclid(v[i], centrale[1]);
//        for(int j = 2; j <= n; j++){
//            dist[i] = min(dist[i], euclid(v[i], centrale[j]));
//        }
//    }
//    long double total = 0;
//    for(int i = 1; i <= m; i++){
//        int aux = 0;
//        for(int j = 1; j <= m; j++){
//            if(dist[i] != 0){
//                if(aux == 0){
//                    aux = j;
//                }
//                else{
//                    if(dist[aux] > dist[j]){
//                        aux = j;
//                    }
//                }
//            }
//        }
//
//        total += dist[aux];
//
//        for(int j = 2; j <= m; j++){
//            dist[j] = min(dist[j], euclid(v[aux], v[j]));
//        }
//    }
//    fout <<fixed<<setprecision(7)<< total;
//    return 0;
//}

// Problema 2 , TEMA 2 : "https://www.infoarena.ro/problema/disjoint"____________________________________________________________________________________________________________


//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//
//int tata[100005];
//int inalt[100005];
//int n, m;
//int x, y, op;
//
//int getRadacina(int nod){
//    if(tata[nod] == 0){
//        return nod;
//    }
//    else{
//        return getRadacina(tata[nod]);
//    }
//}
//
//void uneste(int x, int y){
//    int rx = getRadacina(x);
//    int ry = getRadacina(y);
//    if(inalt[rx] > inalt[ry]){
//        tata[ry] = rx;
//    }
//    else if(inalt[ry] > inalt[rx]){
//        tata[rx] = ry;
//    }
//    else{
//        tata[ry] = rx;
//        inalt[rx]++;
//    };
//}
//
//void verifica(int x, int y){
//    if(getRadacina(x) == getRadacina(y)){
//        fout<<"DA"<<endl;
//    }
//    else{
//        fout<<"NU"<<endl;
//    }
//}
//
//int main()
//{
//   fin >> n >> m;
//   for(int i = 1; i <= m ; i++){
//       int x, y, operatie;
//       fin >> operatie >> x >> y;
//       if(operatie == 1){
//            uneste(x, y);
//       }
//       else{
//           verifica(x, y);
//       }
//   }
//    return 0;
//}

// Problema 4 , TEMA 2 : "https://leetcode.com/problems/path-with-maximum-probability/description/"____________________________________________________________________________________________________________

//
//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//const int MAX = 100001;  // Dimensiunea maximă a vectorului de adiacență
//int n, m, start, target;
//vector<pair<int, double>> adj[MAX];
//
//double probability[100001];
//
//priority_queue<pair<double , int>, vector<pair<double , int>>> q;
//
//double BFS(int node, int end){
//    q.push({1.0, node});
//    probability[node] = 1.0;
//    while(!q.empty()){
//        double cur_prob = q.top().first;
//        int nod = q.top().second;
//        q.pop();
//        if (nod == end) {
//            return cur_prob;
//        }
//        for(auto vecin : adj[nod]){
//            double new_prob = cur_prob * vecin.second;
//            if(new_prob > probability[vecin.first]){
//                probability[vecin.first] = new_prob;
//                q.push({new_prob, vecin.first});
//            }
//        }
//    }
//    return 0.0;
//}
//
//int main()
//{
//    fin >> n >> m;
//    for(int i = 1; i <= m; i++){
//        int x, y;
//        double prob;
//        fin >> x >> y >> prob;
//        adj[x].push_back({y, prob});
//        adj[y].push_back({x, prob});
//    }
//    fin >> start >> target;
//    fout<< fixed << setprecision(2) <<BFS(start, target);
//
//    return 0;
//}

// Problema 10 , TEMA 2 : "https://infoarena.ro/problema/apm2"____________________________________________________________________________________________________________

//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("apm2.in");
//ofstream fout("apm2.out");
//
//const int MAX = 1e5 + 1;
//int n, m, q, tata[10001], dist[10001], maxim[10001], ans[MAX];
//vector<int> adj[MAX];
//
//struct drum{
//    int x, y, taxa;
//}tx[MAX], queries[MAX];
//
//int compara(drum d1, drum d2){
//    return d1.taxa < d2.taxa;
//}
//int root(int a){
//    if(tata[a] == a){
//        return a;
//    }
//    return root(tata[a]);
//}
//
//int uneste(int a, int b){
//    int rd1 = root(a);
//    int rd2 = root(b);
//    if(rd1 != rd2){
//        if(dist[rd1] < dist[rd2]){
//            tata[rd1] = rd2;
//        }
//        else if(dist[rd1] > dist[rd2]){
//            tata[rd2] = rd1;
//        }
//        else{
//            tata[rd1] = rd2;
//            dist[rd2]++;
//        }
//    }
//}
//
//
//
//int main()
//{
//    fin >> n >> m >> q;
//    for(int i = 1; i <= m; i++){
//        fin >> tx[i].x >> tx[i].y >> tx[i].taxa;
//    }
//    sort(tx + 1, tx + m + 1, compara);
//    for(int i = 1; i <= q; i++){
//        fin >> queries[i].x >> queries[i].y;
//    }
//    for(int i = 1; i <= n; i++){
//        tata[i] = i;
//        dist[i] = 1;
//    }
//    for(int i = 1; i <= m; i++){
//        int tata1 = root(tx[i].x);
//        int tata2 = root(tx[i].y);
//        if(tata1 != tata2){
//            uneste(tata1, tata2);
//            for(int j = 1; j <= q; j++){
//                if(!queries[j].taxa && root(queries[j].x) == root(queries[j].y)){
//                    queries[j].taxa = 1;
//                    ans[j] = tx[i].taxa - 1;
//                }
//            }
//        }
//    }
//    for(int i = 1; i <= q; i++){
//        fout << ans[i] << '\n';
//    }
//
//
//    return 0;
//}

// Problema 1 Edmonds Karp, TEMA 2 : "https://www.infoarena.ro/problema/maxflow"____________________________________________________________________________________________________________


//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("maxflow.in");
//ofstream fout("maxflow.out");
//
//
//const int MAXN = 1001; // Numărul maxim de noduri
//const int INF = 1e9; // O valoare mare reprezentând "infinit"
//
//int capacity[MAXN][MAXN]; // Matricea de capacitate
//int parent[MAXN]; // Vectorul de părinți folosit în BFS
//vector<int> adj[MAXN]; // Lista de adiacență
//
//// Implementare BFS pentru a găsi drumul de augmentare
//bool bfs(int source, int sink) {
//    memset(parent, -1, sizeof(parent));
//    parent[source] = source;
//    queue<pair<int, int>> q;
//    q.push({source, INF});
//
//    while (!q.empty()) {
//        int cur = q.front().first;
//        int flow = q.front().second;
//        q.pop();
//
//        for (int next : adj[cur]) {
//            if (parent[next] == -1 && capacity[cur][next]) {
//                parent[next] = cur;
//                int new_flow = min(flow, capacity[cur][next]);
//                if (next == sink)
//                    return true;
//                q.push({next, new_flow});
//            }
//        }
//    }
//    return false;
//}
//
//// Implementare Edmonds-Karp
//int edmonds_karp(int source, int sink) {
//    int flow = 0;
//    while (bfs(source, sink)) {
//        int new_flow = INF;
//        for (int cur = sink; cur != source; cur = parent[cur]) {
//            int prev = parent[cur];
//            new_flow = min(new_flow, capacity[prev][cur]);
//        }
//
//        flow += new_flow;
//
//        for (int cur = sink; cur != source; cur = parent[cur]) {
//            int prev = parent[cur];
//            capacity[prev][cur] -= new_flow;
//            capacity[cur][prev] += new_flow;
//        }
//    }
//    return flow;
//}
//
//void dfs(int node, bool visited[]) {
//    visited[node] = true;
//    for (int next : adj[node]) {
//        if (!visited[next] && capacity[node][next] > 0) {
//            dfs(next, visited);
//        }
//    }
//}
//
//// Afișarea tăieturii minime
//void printMinCut(int source, int n) {
//    bool visited[MAXN] = {false};
//    dfs(source, visited);
//
//    cout << "Tăietura minimă este formată din arcele:\n";
//    for (int i = 0; i < n; i++) {
//        for (int j : adj[i]) {
//            if (visited[i] && !visited[j]) {
//                cout << i << " -> " << j << "\n";
//            }
//        }
//    }
//}
//
//int main() {
//    int n, m;
//    fin >> n >> m;
//    for (int i = 0; i < m; i++) {
//        int u, v, c;
//        fin >> u >> v >> c;
//        adj[u].push_back(v);
//        adj[v].push_back(u); // Adăugăm și muchia inversă pentru rețeaua reziduală
//        capacity[u][v] += c; // Folosim += pentru a gestiona muchii multiple
//    }
//
//
//    int max_flow = edmonds_karp(1, n);
//    fout << max_flow << endl;
//    printMinCut(1, n);
//    return 0;
//}

// Problema 2 Edmonds Karp - CUPLAJ MAXIM, TEMA 2 : "https://www.infoarena.ro/problema/cuplaj"____________________________________________________________________________________________________________
//#include <bits/stdc++.h>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const char iname[] = "cuplaj.in";
const char oname[] = "cuplaj.out";

#define MAXN  20005
#define FOR(i, a, b)  for (int i = (int)(a); i <= (int)(b); ++ i)

struct list {
    int node, cap, flow;
    list *nxt, *dup;
} ;

typedef list* plist;

plist adj[MAXN], edge[MAXN];    int n, m, q[MAXN], sel[MAXN], src, sink;


void alloc_edge(plist &nou, plist &dup, int i, int j)
{
    nou = new list, dup = new list;
    nou->node = j, dup->node = i;
    nou->dup = dup, dup->dup = nou;
    nou->nxt = adj[i], dup->nxt = adj[j];
    adj[i] = nou, adj[j] = dup;
}

void read_in(void)
{
    FILE *fi = fopen(iname, "r");
    int cnt_edges, x, y;
    plist nou, dup;

    fscanf(fi, "%d %d %d", &n, &m, &cnt_edges);
    for (; cnt_edges --; )
    {
        fscanf(fi, "%d %d", &x, &y);
        alloc_edge(nou, dup, x, y + n);
        nou->cap = 1, nou->flow = dup->cap = dup->flow = 0;
    }
    fclose(fi);

    src = 0;
    FOR (i, 1, n) {
        alloc_edge(nou, dup, src, i);
        nou->cap = 1, nou->flow = dup->cap = dup->flow = 0;
    }
    sink = n+m+1;
    FOR (i, n + 1, n + m) {
        alloc_edge(nou, dup, i, sink);
        nou->cap = 1, nou->flow = dup->cap = dup->flow = 0;
    }
}

int BFS(const int src, const int sink)
{
    int h, t;
    plist it;

    memset(sel, 0, sizeof(sel));

    edge[src] = 0;
    for (sel[q[h = t = 0] = src] = 1; h <= t; ++ h)
    {
        for (it = adj[q[h]]; it; it = it->nxt)
            if ((it->cap - it->flow) > 0 && !sel[it->node])
            {
                sel[q[++ t] = it->node] = 1;
                edge[it->node] = it;
                if (it->node == sink)
                {
                    for (it = edge[sink]; it; it = edge[it->dup->node])
                        it->flow ++, it->dup->flow --;
                    return 1;
                }
            }
    }
    return 0;
}

int main(void)
{
    read_in();
    int cuplaj = 0;
    while (BFS(src, sink))  cuplaj ++;

    FILE *fo = fopen(oname, "w");
    fprintf(fo, "%d\n", cuplaj);
    FOR (i, 1, n)
    {
        for (plist it = adj[i]; it; it = it->nxt)
            if (it->flow == 1)
                fprintf(fo, "%d %d\n", i, it->node - n);
    }
    fclose(fo);

    return 0;
}