package uk.ac.aber.cs31920.assignment.implementation;

import uk.ac.aber.cs31920.assignment.implementation.datastructures.Edge;
import uk.ac.aber.cs31920.assignment.implementation.datastructures.MaxFlowGraph;
import uk.ac.aber.cs31920.assignment.implementation.datastructures.ProblemGrid;
import uk.ac.aber.cs31920.assignment.implementation.factories.GraphFactory;
import uk.ac.aber.cs31920.assignment.implementation.factories.GridFactory;
import uk.ac.aber.cs31920.assignment.implementation.solvers.MaxMatchingSolver;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        // get file
        Scanner scan = new Scanner(System.in);
        String filePath = scan.nextLine();

        // read file
        String input = readFile(filePath);

        // compute problem
        ProblemGrid grid = GridFactory.createGridFromString(input);
        MaxFlowGraph graph = GraphFactory.createGraphFromProblemGrid(grid);
        List<Edge> result = MaxMatchingSolver.Solve(graph);


        // print result
        if (result == null){
            System.out.println("no solution");
            return;
        }

        StringBuilder outputBuilder = new StringBuilder();
        for (Edge edge : result){
            outputBuilder.append(edge + " ");
        }
        System.out.println(outputBuilder);
    }

    /**
     * Reads data from given file
     * @param filePath path to file
     * @return data from file
     */
    private static String readFile(String filePath){
        BufferedReader br;
        StringBuilder inputBuilder = new StringBuilder();
        String input;
        try {
            br = new BufferedReader(new FileReader(filePath));
            while (br.ready()) {
                inputBuilder.append(br.readLine()+"\n");
            }
            input = inputBuilder.toString();
        } catch (IOException e){
            throw new RuntimeException(e);
        }
        return input;
    }
}