Problem: There are n cities and m two-way roads in Berland, each road connecting two distinct cities.

Recently the Berland government has made a tough decision to transfer ownership of the roads to private companies. In total, there are 100500 private companies in Berland, numbered by integers from 1 to 100500. After the privatization, every road should belong to exactly one company.

The anti-monopoly committee demands that after the privatization each company can own at most two roads. The urbanists of Berland also stated their opinion: each city should be adjacent to the roads owned by at most k companies.

Help the government to distribute the roads between the companies so that both conditions are satisfied. That is, each company gets at most two roads, and each city has roads of at most k distinct companies adjacent to it.

Input

Input contains one or several test cases. The first line contains an integer t (1 ≤ t ≤ 300) — the number of test cases in the input. Solve test cases separately, test cases are completely independent and do not affect each other.

The following lines describe the test cases. Each case starts with a line consisting of three space-separated integers n, m and k (2 ≤ n ≤ 600, 1 ≤ m ≤ 600, 1 ≤ k ≤ n - 1) — the number of cities, the number of roads and the maximum diversity of the roads adjacent to a city.

Then m lines follow, each having a pair of space-separated integers a_i, b_i (1 ≤ a_i, b_i ≤ n; a_i ≠ b_i). It means that the i-th road connects cities a_i and b_i. All roads are two-way. There is at most one road between a pair of the cities.

The sum of n values for all test cases doesn't exceed 600. The sum of m values for all test cases doesn't exceed 600.

Output

Print t lines: the i-th line should contain the answer for the i-th test case. For a test case, print a sequence of integers c_1, c_2, ..., c_m separated by space, where c_i (1 ≤ c_i ≤ 100500) is the company which owns the i-th road in your plan. If there are multiple solutions, output any of them. If there is no solution for a test case, print c_1=c_2=…=c_m=0.

Example

Input

3
3 3 2
1 2
2 3
3 1
4 5 2
1 2
1 3
1 4
2 3
2 4
4 6 2
1 2
1 3
1 4
2 3
2 4
3 4


Output

1 2 3 
2 1 1 2 3 
0 0 0 0 0 0 

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;

public class Solution
{
    static InputReader in;
    static PrintWriter out;
    
    public static void main(String[] args)
    {

        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        
        int t = in.nextInt();
        
        while(t-- > 0) {
            int n = in.nextInt();
            int m = in.nextInt();
            int k = in.nextInt();
            
            List<Edge>[] g = createGraph(n + m + 2);
            int[] u = new int[m];
            int[] v = new int[m];
            int[] deg = new int[n];
            int[] color = new int[m];
            
            for(int i = 0; i < m; i++) {
                u[i] = in.nextInt() - 1;
                v[i] = in.nextInt() - 1;
                deg[u[i]]++;
                deg[v[i]]++;
                color[i] = i;
            }
            
            boolean ok = true;
            int tot = 0;
            for(int i = 0; i < n; i++) {
                if(deg[i] > 2 * k) {
                    ok = false;
                    break;
                }
                int x = Math.max(2 * (deg[i] - k), 0);
                tot += x;
                addEdge(g, n + m, i, x);
            }
            
            if(!ok) {
                for(int i = 0; i < m; i++)
                    out.print(0 + " ");
                out.println();
                continue;
            }
            
            for(int i = 0; i < m; i++) {
                addEdge(g, u[i], i + n, 1);
                addEdge(g, v[i], i + n, 1);
                addEdge(g, i + n, n + m + 1, 1);
            }
            int flow = maxFlow(g, n + m, n + m + 1);

            if(flow != tot) {
                for(int i = 0; i < m; i++)
                    out.print(0 + " ");
                out.println();
                continue;
            }
            
            ArrayList<Integer> list = new ArrayList<>();
            for(int i = 0; i < n; i++) {
                list.clear();
                for(Edge e: g[i]) {
                    if(e.t == n + m) continue;
//                    debug(i,e);
                    if(e.f > 0) list.add(e.t - n);
                }
                for(int j = 0; j < list.size(); j += 2)
                    color[list.get(j)] = list.get(j + 1);
            }
            for(int c: color) out.print((c + 1) + " ");
            out.println();
        }
        
        out.close();
    }
    
    
    static class Edge
    {
        int t, rev, cap, f;

        public Edge(int t, int rev, int cap)
        {
            this.t = t;
            this.rev = rev;
            this.cap = cap;
        }

        @Override
        public String toString() {
            return t + " " + f + " " + rev + " " + cap;
        }
    }

    public static List<Edge>[] createGraph(int nodes)
    {
        List<Edge>[] graph = new List[nodes];
        for (int i = 0; i < nodes; i++)
            graph[i] = new ArrayList<>();
        return graph;
    }

    public static void addEdge(List<Edge>[] graph, int s, int t, int cap) 
    {
        graph[s].add(new Edge(t, graph[t].size(), cap));
        graph[t].add(new Edge(s, graph[s].size() - 1, 0));
    }

    static boolean dinicBfs(List<Edge>[] graph, int src, int dest, int[] dist) 
    {
        Arrays.fill(dist, -1);
        dist[src] = 0;
        int[] Q = new int[graph.length];
        int sizeQ = 0;
        Q[sizeQ++] = src;
        for (int i = 0; i < sizeQ; i++) {
            int u = Q[i];
            for (Edge e : graph[u]) {
                if (dist[e.t] < 0 && e.f < e.cap) {
                    dist[e.t] = dist[u] + 1;
                    Q[sizeQ++] = e.t;
                }
            }
        }
        return dist[dest] >= 0;
    }

    static int dinicDfs(List<Edge>[] graph, int[] ptr, int[] dist, int dest, int u, int f)
    {
        if (u == dest)
            return f;
        for (; ptr[u] < graph[u].size(); ++ptr[u]) {
            Edge e = graph[u].get(ptr[u]);
            if (dist[e.t] == dist[u] + 1 && e.f < e.cap) {
                int df = dinicDfs(graph, ptr, dist, dest, e.t, Math.min(f, e.cap - e.f));
                if (df > 0) {
                    e.f += df;
                    graph[e.t].get(e.rev).f -= df;
                    return df;
                }
            }
        }
        return 0;
    }

    public static int maxFlow(List<Edge>[] graph, int src, int dest)
    {
        int flow = 0;
        int[] dist = new int[graph.length];
        while (dinicBfs(graph, src, dest, dist)) {
            int[] ptr = new int[graph.length];
            while (true) {
                int df = dinicDfs(graph, ptr, dist, dest, src, Integer.MAX_VALUE);
                if (df == 0)
                    break;
                flow += df;
            }
        }
      return flow;

    }
    
    static void debug(Object... o)
    {
            System.out.println(Arrays.deepToString(o));
    }

    static class InputReader
    {

        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream)
        {
                this.stream = stream;
        }

        public int snext()
        {
                if (snumChars == -1)
                        throw new InputMismatchException();
                if (curChar >= snumChars)
                {
                        curChar = 0;
                        try
                        {
                                snumChars = stream.read(buf);
                        } catch (IOException e)
                        {
                                throw new InputMismatchException();
                        }
                        if (snumChars <= 0)
                                return -1;
                }
                return buf[curChar++];
        }

        public int nextInt()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-')
                {
                        sgn = -1;
                        c = snext();
                }
                int res = 0;
                do
                {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public long nextLong()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-')
                {
                        sgn = -1;
                        c = snext();
                }
                long res = 0;
                do
                {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public int[] nextIntArray(int n)
        {
                int a[] = new int[n];
                for (int i = 0; i < n; i++)
                {
                        a[i] = nextInt();
                }
                return a;
        }

        public long[] nextLongArray(int n)
        {
                long a[] = new long[n];
                for (int i = 0; i < n; i++)
                {
                        a[i] = nextLong();
                }
                return a;
        }

        public String readString()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                StringBuilder res = new StringBuilder();
                do
                {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isSpaceChar(c));
                return res.toString();
        }

        public String nextLine()
        {
                int c = snext();
                while (isSpaceChar(c))
                        c = snext();
                StringBuilder res = new StringBuilder();
                do
                {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isEndOfLine(c));
                return res.toString();
        }

        public boolean isSpaceChar(int c)
        {
                if (filter != null)
                        return filter.isSpaceChar(c);
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c)
        {
                return c == '\n' || c == '\r' || c == -1;
        }

        public interface SpaceCharFilter
        {
                public boolean isSpaceChar(int ch);
        }

    }
}