POLSKI SPOJ

Odwzorowanie c przyporządkowujące wierzchołkom grafu G liczby 1,...,k nazywać będziemy k-pokolorowaniem (wierzchołkowym) grafu G, jeżeli dla każdej pary wierzchołków sąsiednich (połączonych krawędzią) u,v mamy, że c(u) jest różne od c(v). Twoim zadaniem jest znaleźć dowolne 6-pokolorowanie podanego grafu planarnego.

Wejście

Pierwsza linia zawiera liczbę całkowitą 1<=t<=100 oznaczająca liczbę zestawów testowych. Następnie podanych jest t grafów planarnych. Każdy z grafów opisany jest w dwóch liniach. Pierwsza linia zawiera napis:

Graph with n nodes and m edges: [graf z n wierzchołkami oraz m krawędziami]

W drugiej linii wypisane są krawędzie grafu oddzielone przecinkami. Każda krawędź podana jest jako para wierzchołków: {u,v}. Wierzchołki grafu numerujemy kolejnymi liczbami: 0...,n-1.
Tekst w nawiasach [ ] nie występuje w plikach wejściowych ani wyjściowych.

Wyjście

Dla każdego przypadku testowego podaj 6-kolorowanie odpowiedniego grafu planarnego. Pokolorowanie grafu o n wierzchołkach powinno być podane w kolejnych n liniach, z których każda zawiera dwie liczby całkowite v c(v), oznaczające numer wierzchołka oraz wartość koloru przydzielonego temu wierzchołkowi.

Przykład

Wejście:
2
Graph with 3 nodes and 3 edges: [graf z 3 wierzchołkami i 3 krawędziami]
{0,1},{1,2},{2,0}
Graph with 9 nodes and 14 edges: [graf z 9 wierzchołkami i 14 krawędziami]
{0,1},{0,2},{0,5},{0,8},{1,2},{2,3},{2,4},{3,4},{4,5},{4,8},{5,6},{5,7},{5,8},{6,7}

Wyjście:
0 1
1 2
2 3

0 1
1 2
2 3
3 4
4 5
5 3
6 1
7 4
8 2

Wskazówki

Algorytm SL (Smallest Last) rozwiązuje sformułowany problem.

A function c mapping the set of vertices of a graph G into integers 1,...,k is called a k-coloring of G if for every pair of adjacent vertices u,v we have that c(u) is not equal to c(v). Find 6-coloring of a given planar graph.

Input

The first line contains an integer 1<=t<=100 denoting the number of test cases. Then, t planar graphs are given. Each graph is described by two lines. First line contains a string of the form:

Graph with n nodes and m edges:

The second line gives the edges of the graph separated with commas. Each edge is given as a pair of vertices: {u,v}. Vertices of the graph are denoted with integers 0...,n-1.

Output

For each test case print a 6-coloring of the corresponding planar graph. The coloring of a graph with n vertices shoud be given in n lines, where each line contains two integers

v c(v)

the number of a vertex and the color assigned to this vertex.

Example

Input:
2
Graph with 3 nodes and 3 edges:
{0,1},{1,2},{2,0}
Graph with 9 nodes and 14 edges:
{0,1},{0,2},{0,5},{0,8},{1,2},{2,3},{2,4},{3,4},{4,5},{4,8},{5,6},{5,7},{5,8},{6,7}

Output:
0 1
1 2
2 3

0 1
1 2
2 3
3 4
4 5
5 3
6 1
7 4
8 2

Hints

The SL algorithm (Smallest Last) solves the problem