/**
 * Dany jest graf w postaci
 * w pierwszym wierszu zapisane są dwie liczby całkowite n i m
 * odpowiednio liczba wierzchołków (2 <= n <= 1000)
 * oraz liczba krawędzi (2 <= m <= 100000)
 * W kolejnych m wierszach zapisane są krawędzie.
 * Każdy z m wierszy zawiera dwie liczby całkowite a_i i b_i,
 * oznaczające, że wierzchołki a_i i b_i są połączone krawędzią.
 *
 * Należy wyznaczyć podział wierzchołków grafu na rozłączone zbiory
 * V_1, V_2, \ldots, V_k
 * tak by:
 * - zmaksymalizować liczbę podzbiorów
 * - jeśli a \in V_i, b\in V_j oraz i<>j, to wierzchołki a i b muszą
 *   być połączone krawędzią
 *
 * Oczekiwany format wyjścia:
 * jedna liczba całkowita - maksymalna liczba podzbiorów
 */


import org.junit.Assert.*;
import static org.junit.Assert.assertEquals;
import org.junit.Test;

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


public class zadanieGrafoweTest {

    private ByteArrayOutputStream outContent;;

    private void setUpStreams(String inp) {
        outContent = new ByteArrayOutputStream();
        System.setOut(new PrintStream(outContent));
        System.setIn(new ByteArrayInputStream(inp.getBytes()));
    }

    private void cleanUpStreams() {
        System.setOut(null);
        System.setIn(null);
    }

    private String runProgram(String inp) {
        try {
            setUpStreams(inp);
            Main.main(new String[0]);
            return outContent.toString();
        } finally {
            cleanUpStreams();
        }
    }

    @Test
    public void testGrafPelny() {
      testuj("3 3\n1 2\n3 1\n3 2\n",3);
    }

    @Test
    public void testKwadrat() {
      testuj("4 4\n1 2\n3 4\n2 3\n4 1\n",2);
    }

    @Test
    public void testKwadratZPowtorzonaKrawedzia() {
      testuj("4 5\n1 2\n2 1\n3 4\n2 3\n4 1\n",2); // krawędz 1-2 jest powtórzona!
    }


    @Test
    public void testKoperta() {
      // 1---------6
      // |\       /|
      // | 3-----4 |
      // |/       \|
      // 2---------5
      testuj("6 9\n1 2\n2 3\n3 1\n3 4\n\n4 5\n5 6\n6 4\n1 6\n2 5\n",1);
    }

    @Test
    public void testGrafPusty3() {
      testuj("3 0\n",1);
    }

    @Test
    public void testGrafPusty100() {
      testuj("100 0\n",1);
    }

    @Test(timeout=2000)
    public void testGrafPusty1000() {
      testuj("1000 0\n",1);
    }

    @Test(timeout=2000)
    public void testGrafPusty10000() {
      testuj("10000 0\n",1);
    }

    @Test(timeout=2000)
    public void testGrafJednaKrawedzN10000() {
      testuj("10000 1\n1 2\n",1);
    }

    private void testuj(String inp, int odp) {
        String should_be=""+odp+"\n";
        assertEquals(should_be, runProgram(inp));
    }


}