// 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 <iostream>
//#include <fstream>
//#include <vector>
//#include <queue>
//#include <cstring>
//
//using namespace std;
//
//const int MAXN = 20005;
//
//struct Edge {
// int to, capacity, flow, reverseIndex;
//};
//
//int n, m, source, sink;
//vector<Edge> adj[MAXN];
//int parent[MAXN];
//int edgeIndex[MAXN];
//
//void addEdge(int from, int to, int capacity) {
// adj[from].push_back({to, capacity, 0, (int)adj[to].size()});
// adj[to].push_back({from, 0, 0, (int)adj[from].size() - 1});
//}
//
//int BFS() {
// memset(parent, -1, sizeof(parent));
// parent[source] = source;
//
// queue<int> q;
// q.push(source);
//
// while (!q.empty()) {
// int current = q.front();
// q.pop();
//
// for (int i = 0; i < adj[current].size(); i++) {
// Edge &edge = adj[current][i];
// if (parent[edge.to] == -1 && edge.capacity > edge.flow) {
// parent[edge.to] = current;
// edgeIndex[edge.to] = i;
// q.push(edge.to);
//
// if (edge.to == sink) {
// return 1;
// }
// }
// }
// }
// return 0;
//}
//
//int main() {
// ifstream fin("cuplaj.in");
// ofstream fout("cuplaj.out");
//
// int numEdges;
// fin >> n >> m >> numEdges;
//
// source = 0;
// sink = n + m + 1;
//
// for (int i = 0; i < numEdges; ++i) {
// int u, v;
// fin >> u >> v;
// addEdge(u, n + v, 1);
// }
//
// for (int i = 1; i <= n; i++) {
// addEdge(source, i, 1);
// }
//
// for (int i = 1; i <= m; i++) {
// addEdge(n + i, sink, 1);
// }
//
// while (BFS()) {
// int v = sink;
// while (v != source) {
// int u = parent[v];
// adj[u][edgeIndex[v]].flow += 1;
// adj[v][adj[u][edgeIndex[v]].reverseIndex].flow -= 1;
// v = u;
// }
// }
//
// int maxFlow = 0;
// for (Edge &edge : adj[source]) {
// maxFlow += edge.flow;
// }
//
// fout << maxFlow << "\n";
// for (int i = 1; i <= n; i++) {
// for (Edge &edge : adj[i]) {
// if (edge.flow == 1) {
// fout << i << " " << edge.to - n << "\n";
// break;
// }
// }
// }
//
// fin.close();
// fout.close();
// return 0;
//}
//
// Problema 2 , TEMA 2 : "https://www.infoarena.ro/problema/harta"____________________________________________________________________________________________________________
//#include <fstream>
//#include <algorithm>
//using namespace std;
//
//struct City {
// int incomingRoutes, position;
//};
//
//bool compare(City a, City b) {
// if(a.incomingRoutes == b.incomingRoutes)
// return a.position > b.position;
// return a.incomingRoutes > b.incomingRoutes;
//}
//
//int main()
//{
// ifstream fin("harta.in");
// ofstream fout("harta.out");
//
// int totalCities, totalRoutes = 0;
// fin >> totalCities;
//
// int incoming[105], outgoing[105];
// City cityInfo[105];
//
// // Reading incoming and outgoing routes for each city and calculating total routes
// for(int i = 1; i <= totalCities; ++i) {
// fin >> outgoing[i] >> incoming[i];
// totalRoutes += outgoing[i];
// }
//
// fout << totalRoutes << "\n";
//
// // Calculating the routes between cities
// for(int i = 1; i <= totalCities; ++i) {
// // Filling the cityInfo structure with data for sorting
// for(int j = 1; j <= totalCities; ++j)
// cityInfo[j] = {incoming[j], j};
//
// // Sorting the cities based on the number of incoming routes in descending order
// sort(cityInfo + 1, cityInfo + totalCities + 1, compare);
//
// // Finding and printing possible routes
// for(int j = 1; j <= totalCities && outgoing[i]; ++j)
// if(cityInfo[j].position != i){
// fout << i << " " << cityInfo[j].position << "\n";
// incoming[cityInfo[j].position]--;
// outgoing[i]--;
// }
// }
//
// return 0;
//}
// Problema 8 , TEMA 2 : "https://infoarena.ro/problema/fmcm"____________________________________________________________________________________________________________
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <algorithm>
using namespace std;
const int MAXN = 351;
const int INF = 1e9;
struct Edge {
int from, to, capacity, cost, flow = 0;
};
vector<Edge> edges;
vector<int> graph[MAXN];
int dist[MAXN], parent[MAXN];
bool inQueue[MAXN];
void addEdge(int u, int v, int capacity, int cost) {
graph[u].push_back(edges.size());
edges.push_back({u, v, capacity, cost, 0});
graph[v].push_back(edges.size());
edges.push_back({v, u, 0, -cost, 0});
}
bool dijkstra(int source, int destination, int N) {
fill(dist, dist + N + 1, INF);
fill(parent, parent + N + 1, -1);
dist[source] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, source});
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d != dist[u]) continue;
for (int id : graph[u]) {
if (edges[id].capacity > edges[id].flow &&
dist[u] + edges[id].cost < dist[edges[id].to]) {
dist[edges[id].to] = dist[u] + edges[id].cost;
parent[edges[id].to] = id;
pq.push({dist[edges[id].to], edges[id].to});
}
}
}
return parent[destination] != -1;
}
int minCostMaxFlow(int source, int destination, int N) {
int flow = 0;
int cost = 0;
while (dijkstra(source, destination, N)) {
int f = INF;
for (int u = destination; u != source; u = edges[parent[u]].from) {
f = min(f, edges[parent[u]].capacity - edges[parent[u]].flow);
}
for (int u = destination; u != source; u = edges[parent[u]].from) {
edges[parent[u]].flow += f;
edges[parent[u]^1].flow -= f;
cost += f * edges[parent[u]].cost;
}
flow += f;
}
return cost;
}
int main() {
ifstream input("fmcm.in");
ofstream output("fmcm.out");
int N, M, S, D;
input >> N >> M >> S >> D;
for (int i = 0; i < M; ++i) {
int x, y, c, z;
input >> x >> y >> c >> z;
addEdge(x, y, c, z);
}
int result = minCostMaxFlow(S, D, N);
output << result << "\n";
return 0;
}
Stanciu Carol Carol7237