Saturday, May 25, 2013

Codeforces Round #181 (Div. 2) B Coach

//Codeforces Round #181 (Div. 2) B Coach

import java.io.*;
import java.math.*;
import java.util.*;

//Codeforces
public class MainCodeforces1 {
    private static MyScanner in;
    private static PrintStream out;
    private static boolean LOCAL_TEST = false;

    private static void solve() throws IOException
    {
        int n = in.nextInt();
        int m = in.nextInt();
        int[] group = new int[n + 1];
        int grpid = 0;
        for (int i = 0; i < m; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            if (group[a] == 0 && group[b] == 0) {
                grpid++;
                group[a] = group[b] = grpid;
            }
            else {
                if (group[a] == 0)
                    group[a] = group[b];
                else if (group[b] == 0)
                    group[b] = group[a];
                else {
                    if (group[a] != group[b]) {
                        out.println(-1);
                        return;
                    }
                }
            }
        }
        ArrayList<Integer>[] grpMembers = new ArrayList[grpid + 1];
        for (int i = 1; i < grpMembers.length; i++) {
            grpMembers[i] = new ArrayList<Integer>();
        }
        ArrayList<Integer> anygroup = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            int grp = group[i];
            if (grp > 0)
                grpMembers[grp].add(i);
            else
                anygroup.add(i);
        }
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        int anyGroupTaken = 0;
        for (int i = 1; i < grpMembers.length; i++) {
            if (grpMembers[i].size() > 3) {
                out.println(-1);
                return;
            }
            else if (grpMembers[i].size() == 3) {
                result.add(grpMembers[i]);
            }
            else {
                if (anyGroupTaken >= anygroup.size()) {
                    out.println(-1);
                    return;
                }
                int addAny = 3 - grpMembers[i].size();
                for (int j = 0; j < addAny; j++) {
                    grpMembers[i].add(anygroup.get(anyGroupTaken++));
                }
                result.add(grpMembers[i]);
            }
        }
        while (anyGroupTaken < anygroup.size()) {
            ArrayList<Integer> g = new ArrayList<>();
            for (int i = 0; i < 3; i++) {
                g.add(anygroup.get(anyGroupTaken++));
            }
            result.add(g);
        }
        for (int i = 0; i < result.size(); i++) {
            out.println("" + result.get(i).get(0) +
                    " " + result.get(i).get(1) +
                    " " + result.get(i).get(2));
        }
        out.println();
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        out = System.out;
        try {
            String cname = System.getenv("COMPUTERNAME");
            LOCAL_TEST = (cname.equals("ALPHA530"));
        } catch (Exception e) {
        }
        if (LOCAL_TEST) {
            in = new MyScanner("E:\\zin.txt");
        }
        else {
            boolean usingFileForIO = false;
            if (usingFileForIO) {
                // using input.txt and output.txt as I/O
                in = new MyScanner("input.txt");
                out = new PrintStream("output.txt");
            }
            else {
                in = new MyScanner();
                out = System.out;
            }
        }

        solve();
    }

    // =====================================
    static class MyScanner {
        Scanner inp = null;

        public MyScanner() throws IOException
        {
            inp = new Scanner(System.in);
        }

        public MyScanner(String inputFile) throws IOException {
            inp = new Scanner(new FileInputStream(inputFile));
        }

        public int nextInt() throws IOException {
            return inp.nextInt();
        }

        public long nextLong() throws IOException {
            return inp.nextLong();
        }

        public double nextDouble() throws IOException {
            return inp.nextDouble();
        }

        public String nextString() throws IOException {
            return inp.next();
        }

    }

}

No comments:

Post a Comment