Trilobite adore construire des métros. Il a conçu $n$ lignes, chacune ayant $n+1$ sites potentiels, représentés par des coordonnées dans le plan.
Pour enrichir l'expérience du métro, Trilobite a décidé que chaque ligne serait un segment de droite ! C'est-à-dire que pour chaque ligne, Trilobite choisira exactement deux sites et tracera un segment entre eux. Afin de maximiser la difficulté des correspondances pour les passagers, Trilobite exige que le nombre total d'intersections entre les $n$ lignes construites soit minimisé. Notez que les intersections incluent les points de départ et d'arrivée. Veuillez planifier une solution valide.
En termes simples : étant donné $n$ couleurs de points dans un plan bidimensionnel, avec $n+1$ points pour chaque couleur. Vous devez choisir deux points distincts pour chaque couleur afin de tracer un segment, de telle sorte que le nombre total d'intersections entre les $n$ segments soit minimisé. Affichez une solution de construction.
Remarque : si deux segments sont colinéaires, le nombre d'intersections est défini comme infini. Toutes les valeurs infinies sont considérées comme égales.
Format d'entrée
Ce problème contient plusieurs jeux de tests. La première ligne contient un entier positif $T$ représentant le nombre de jeux de tests. Pour chaque jeu de test :
La première ligne contient un entier positif $n$ représentant le nombre de lignes.
Les $n$ lignes suivantes contiennent chacune $2n+2$ entiers, où les $2i-1$-ième et $2i$-ième entiers $(x_i, y_i)$ identifient les coordonnées d'un site pour la ligne actuelle, et l'indice de ce site est $i$.
Il est garanti que toutes les coordonnées des sites sont distinctes.
Format de sortie
Pour chaque jeu de test, affichez $n$ lignes, chacune contenant deux entiers positifs, indiquant les indices des deux sites connectés par chaque ligne. Vous n'avez besoin d'afficher qu'une solution arbitraire.
Exemples
Entrée 1
1 2 5 0 0 8 10 8 0 4 10 4 5 12
Sortie 1
1 3 1 3
Remarque
Dans l'image, les points bleus et rouges représentent respectivement les sites de la première et de la deuxième ligne, et les lignes bleue et rouge représentent les segments choisis pour la première et la deuxième ligne.
Notez que vous n'avez besoin d'afficher qu'une solution arbitraire, donc :
1 2 2 3
est également une réponse correcte.
Contraintes
| Sous-tâche | Score | Contraintes supplémentaires |
|---|---|---|
| 1 | 30 | $n\le 5, \sum n\le 50$ |
| 2 | 20 | Il existe une permutation des $n(n+1)$ points telle que les coordonnées du $i$-ième point sont exactement $(i, i)$ |
| 3 | 20 | $n\leq 100$ |
| 4 | 30 | Aucune |
Pour toutes les données : $1\le n\le 1000, \sum n\leq 2000$, $|x_i|, |y_i|\le 10^9$.