SP243 STABLEMP - Stable Marriage Problem

There are given _n_ men and _n_ women. Each woman ranks all men in order of her preference (her first choice, her second choice, and so on). Similarly, each man sorts all women according to his preference. The goal is to arrange _n_ marriages in such a way that if a man _m_ prefers some woman _w_ more than his wife, then _w_ likes her husband more than _m_. In this way, no one leaves his partner to marry somebody else. This problem always has a solution and your task is to find one.

The first line contains a positive integer _t_

For each test case print _n_ lines, where each line contains two numbers _m_ and _w_, which means that the **man** number _m_ and the **woman** number _w_ should get married.