Algorist Club

Members of the Algorist Club take pride in knowing one another well. Every May, when new members join, the club holds a chicken and beer party where the new members get to know the current members and one another. The rule is this. If two members A and B do not know each other, the two of them hold one talk session of 15 minutes. If A knows neither B nor C, then A holds two separate sessions.

The party time is split into slots of 15 minutes. Any number of sessions run at the same time in one slot, but one person holds at most one session per slot. Let A be the member who does not know the largest number of people in the club, and let $k$ be the number of people A does not know. At least $k$ slots are needed. Whether exactly $k$ slots are enough is not known, so the leaders allow $k+1$ slots.

The leaders build the schedule with this rule. They read the pairs of people who do not know each other in the order given in the input, and give each pair the lowest numbered slot in which both people are still free. Only slots 1 through $k+1$ are used. If some pair has no slot in which both people are free, the scheduling fails right there.

Given the pairs of people who do not know each other, write a program that finds the schedule built by this rule.

The input has several test cases. The first line has the number of test cases $T$. The first line of each test case has the number of members $n$ and the number of pairs of people who do not know each other $m$ ($2 \le n \le 444$, $1 \le m \le n(n-1)/2$). The members are numbered from 1 to $n$. Each of the next $m$ lines has the numbers $a$ and $b$ of two members who do not know each other. The pairs come in lexicographic order. That is, $a < b$ always holds, a pair with a smaller $a$ comes earlier, and among the pairs with the same $a$, the one with the smaller $b$ comes earlier.

For each test case, print the pairs given in the input in the same order, one pair per line. On each line print the two member numbers and the slot assigned to that pair, separated by single spaces. For a test case where the scheduling fails, print 0 as the slot of every pair.